这是我本题的AC代码(未加卡常,但正确)
#include <iostream>
#define int long long
using namespace std;
int n,q,w;
int a[200005];
int d[800005],tag[800005];
void build(int s,int t,int p){
if(s==t){
d[p]=a[s];
return ;
}
int mid=(s+t)>>1;
build(s,mid,p<<1);
build(mid+1,t,p<<1|1);
d[p]=d[p<<1]+d[p<<1|1];
}
void update(int l,int r,int c,int s,int t,int p){
if(l<=s&&t<=r){
tag[p]+=c,d[p]+=(t-s+1)*c;
return ;
}
int mid=(s+t)>>1;
if(tag[p]!=0){
d[p<<1]+=(mid-s+1)*tag[p],d[p<<1|1]+=(t-mid)*tag[p];
tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
tag[p]=0;
}
if(l<=mid)
update(l,r,c,s,mid,p<<1);
if(r>mid)
update(l,r,c,mid+1,t,p<<1|1);
d[p]=d[p<<1]+d[p<<1|1];
}
int query(int l,int r,int s,int t,int p){
if(l<=s&&t<=r)
return d[p];
int mid=(s+t)>>1,sum=0;
if(tag[p]!=0){
d[p<<1]+=(mid-s+1)*tag[p],d[p<<1|1]+=(t-mid)*tag[p];
tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
tag[p]=0;
}
if(l<=mid)
sum+=query(l,r,s,mid,p<<1);
if(r>mid)
sum+=query(l,r,mid+1,t,p<<1|1);
return sum;
}
int query2(int cnt,int bld,int s,int t,int p){
if(s==t)
return s;
int mid=(s+t)>>1;
d[p<<1]+=(mid-s+1)*tag[p],d[p<<1|1]+=(t-mid)*tag[p];
tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
tag[p]=0;
if(bld>d[p<<1]*cnt)
return query2(cnt,bld-d[p<<1]*cnt,mid+1,t,p<<1|1);
else
return query2(cnt,bld,s,mid,p<<1);
}
signed main(){
cin>>n>>q>>w;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while(q--){
int l,r,c;
cin>>l>>r>>c;
update(l,r,c,1,n,1);
int cnt=1,ans=0,noww=w;
int now=query(1,n,1,n,1);
while(1){
if(w<=now)
break;
w-=now,now*=2;
ans+=n,cnt*=2;
}
int tmp=query2(cnt,w,1,n,1);
w=noww;
cout<<ans+tmp-1<<endl;
}
return 0;
}
但是当我把
int tmp=query2(cnt,w,1,n,1);
w=noww;
cout<<ans+tmp-1<<endl;
改为
w=noww;
cout<<ans+query2(cnt,w,1,n,1)-1<<endl;
样例却会输出
11
11
11
10
为啥?