如题

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q,W,a[200005],pow_2[65],tree[800005],lazy[800005];
__int128 sum;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
inline void push_up(int id){
	tree[id]=tree[id<<1]+tree[id<<1|1];
}
inline void push_down(int l,int r,int id){
	if(!lazy[id]) return;
	int mid=(l+r)>>1;
	lazy[id<<1]+=lazy[id];
	tree[id<<1]+=(mid-l+1)*lazy[id];
	lazy[id<<1|1]+=lazy[id];
	tree[id<<1|1]+=(r-mid)*lazy[id];
	lazy[id]=0;
}
inline void build(int l,int r,int id){
	if(l==r){
		tree[id]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
	push_up(id);
}
inline void add(int l,int r,int id,int ql,int qr,int num){
	if(ql<=l&&r<=qr){
		tree[id]+=(r-l+1)*num;
		lazy[id]+=num;
		return;
	}
	push_down(l,r,id);
	int mid=(l+r)>>1;
	if(ql<=mid) add(l,mid,id<<1,ql,qr,num);
	if(mid<qr) add(mid+1,r,id<<1|1,ql,qr,num);
	push_up(id);
}
inline int find(int l,int r,int id,int num){
	if(l==r){
		if(tree[id]<num) return 1;
		else return 0;
	}
	push_down(l,r,id);
	int mid=(l+r)>>1;
	if(tree[id]<num) return r-l+1;
	if(tree[id<<1]<num) return (mid-l+1)+find(mid+1,r,id<<1|1,num-tree[id<<1]);
	else return find(l,mid,id<<1,num);
	//push_up(id);
}
signed main(){
	n=read();q=read();W=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		sum+=a[i];
	}
	build(1,n,1);
	pow_2[0]=1;
	for(int i=1;i<=63;i++) pow_2[i]=pow_2[i-1]*2;
	while(q--){
		int l,r,d,bs=1,now=W,ans=0;
		l=read();r=read();d=read();
		sum+=(r-l+1)*d;
		while(now>sum*bs){
			now-=sum*bs;
			bs<<=1;
			ans+=n;
		}
		add(1,n,1,l,r,d);
		now=(now/bs)+(bool)(now%bs);
		cout<<ans+find(1,n,1,now)<<endl;
	}
	return 0;
}