萌新已AC,求问
查看原帖
萌新已AC,求问
676569
WoodReal12楼主2024/10/22 21:51

这是我本题的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

为啥?

2024/10/22 21:51
加载中...