This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
struct line{
int l,r,num;
long long val;
bool operator < (const line &p){
if (val==p.val&&l==p.l)return r<p.r;
if (val==p.val)return l<p.l;
return val<p.val;
}
};
struct arr{
int l,r;
long long sum;
};
struct node{
int l,r;
vector<arr>pf,sf;
vector<line>tmp;
long long sum;
node(){
sum=0;
pf.clear(),sf.clear(),tmp.clear();
}
}st[maxn*4];
long long a[maxn];
node merge(const node &p,const node &q){
if (p.pf.empty())return q;
if (q.pf.empty())return p;
node r;
r.pf=p.pf;
long long sum=0;
for (auto v:p.pf)sum+=v.sum;
for (auto v:q.pf){
if (sum>=a[v.l]){
r.pf.back().sum+=v.sum;
r.pf.back().r=v.r;
sum+=v.sum;
}
else {
r.pf.pb(v);
sum+=v.sum;
}
}
sum=0;
r.sf=q.sf;
for (auto v:q.sf)sum+=v.sum;
for (auto v:p.sf){
if (sum>=a[v.r]){
r.sf.back().sum+=v.sum;
r.sf.back().l=v.l;
sum+=v.sum;
}
else {
r.sf.pb(v);
sum+=v.sum;
}
}
r.sum=p.sum+q.sum;
r.l=p.l,r.r=q.r;
vector<line>temp;
for (auto u:p.tmp){
auto v=u;
if (v.r==p.r){
int i1=0,i2=0;
while (true){
if (i1<sz(p.sf)&&p.sf[i1].l>=v.l){
i1++;
continue;
}
if (i1<sz(p.sf)&&a[p.sf[i1].r]<=v.val){
v.val+=p.sf[i1].sum;
v.l=p.sf[i1].l;
i1++;
continue;
}
if (i2<sz(q.pf)&&a[q.pf[i2].l]<=v.val){
v.val+=q.pf[i2].sum;
v.r=q.pf[i2].r;
i2++;
continue;
}
break;
}
}
if (v.l==r.l||v.r==r.r)temp.pb(v);
}
for (auto u:q.tmp){
auto v=u;
if (v.l==q.l){
int i1=0,i2=0;
while (true){
if (i1<sz(q.pf)&&v.r>=q.pf[i1].r){
i1++;
continue;
}
if (i1<sz(q.pf)&&a[q.pf[i1].l]<=v.val){
v.val+=q.pf[i1].sum;
v.r=q.pf[i1].r;
i1++;
continue;
}
if (i2<sz(p.sf)&&a[p.sf[i2].r]<=v.val){
v.val+=p.sf[i2].sum;
v.l=p.sf[i2].l;
i2++;
continue;
}
break;
}
}
if (v.l==r.l||v.r==r.r)temp.pb(v);
}
sort(all(temp));
while (!temp.empty()){
auto u=temp.back();
temp.pop_back();
if (r.tmp.empty()){
r.tmp.pb(u);
continue;
}
if (r.tmp.back().l==u.l&&r.tmp.back().r==u.r){
r.tmp.back().num+=u.num;
continue;
}
r.tmp.pb(u);
}
return r;
}
void build(int id,int l,int r){
if (l==r){
st[id].l=l,st[id].r=r;
st[id].sum=a[l];
st[id].pf.pb({l,l,a[l]}),st[id].sf.pb({l,l,a[l]});
st[id].tmp.pb({l,l,1,a[l]});
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
st[id]=merge(st[id<<1],st[id<<1|1]);
}
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
st[id].sum=val;
st[id].pf.clear(),st[id].sf.clear(),st[id].tmp.clear();
st[id].pf.pb({l,l,a[l]}),st[id].sf.pb({l,l,a[l]});
st[id].tmp.pb({l,l,1,a[l]});
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,val);
update(id<<1|1,mid+1,r,u,val);
st[id]=merge(st[id<<1],st[id<<1|1]);
}
node get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return node();
if (u<=l&&r<=v)return st[id];
int mid=(l+r)>>1;
return merge(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
int n;
cin>>n;
for1(i,1,n)cin>>a[i];
build(1,1,n);
int q;
cin>>q;
for1(i,1,q){
int t;
cin>>t;
if (t==1){
int x,y;
cin>>x>>y;
a[x]=y;
update(1,1,n,x,y);
}
else {
int l,r;
cin>>l>>r;
node tmp=get(1,1,n,l,r);
for (auto v:tmp.tmp){
if (v.l==l&&v.r==r){
cout<<v.num<<'\n';
}
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |