求调悬关

#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=l;i>=r;--i)
#define int unsigned long long
const int N=2e5+5;
int n,q,W,a[N],Log[N],k,rss=0;
struct seg_T{
	struct node{
		int lz,s;
	}t[N<<2];
	inline int ls(int u){
		return u<<1;
	}
	inline int rs(int u){
		return u<<1|1;
	}
	inline void push_up(int u){
		t[u].s=t[ls(u)].s+t[rs(u)].s;
	}
	inline void build(int u,int l,int r){
		if(l==r){
			t[u].s=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(ls(u),l,mid);
		build(rs(u),mid+1,r);
		push_up(u);
	}
	inline void tag(int u,int l,int r,int k){
		t[u].s+=(r-l+1)*k;
		t[u].lz+=k;
	}
	inline void push_dn(int u,int l,int r){
		if(t[u].lz){
			int mid=(l+r)>>1;
			tag(ls(u),l,mid,t[u].lz);
			tag(rs(u),mid+1,r,t[u].lz);
			t[u].lz=0;
		}
	}
	inline void upd(int u,int l,int r,int ql,int qr,int k){
		if(ql<=l&&qr>=r){
			tag(u,l,r,k);return;
		}
		int mid=(l+r)>>1;
		push_dn(u,l,r);
		if(ql<=mid){
			upd(ls(u),l,mid,ql,qr,k);
		}
		if(qr>mid){
			upd(rs(u),mid+1,r,ql,qr,k);
		}
		push_up(u);
	} 
	inline int query(int u,int l,int r){
		if(l==r){
			return k?l:(l-1);
		}
		int mid=(l+r)>>1;
		push_dn(u,l,r);
		if(t[ls(u)].s*rss>=k){
			return query(ls(u),l,mid);
		}else{
			k-=t[ls(u)].s*rss;
			return query(rs(u),mid+1,r);
		}
	}
	int query_(int u,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r){
			return t[u].s;
		}
		int mid=(l+r)>>1;
		int sum=0;
		push_dn(u,l,r);
		if(ql<=mid) sum+=query_(ls(u),l,mid,ql,qr);
		if(qr>mid) sum+=query_(rs(u),mid+1,r,ql,qr);
		return sum;
	}
}bit; 
inline void sol(){
	int l,r,k,ans=0;
	cin>>l>>r>>k;
	bit.upd(1,1,n,l,r,k);
	int s=bit.query_(1,1,n,1,n),res=0;
	int power=W/s;
	up(i,0,60){
		if((Log[i]==power)&&(W%s==0)){
			cout<<1ll*i*n-1<<'\n';
			return;
		}
		if(Log[i]<=power){
			res=i;
		}else{
			break;
		}
	}
	ans+=1ll*res*n;
//	cout<<res<<'\n';
	rss=1ll<<res;
	k=W-Log[res]*s;
	int an=bit.query(1,1,n);
	cout<<an<<'\n'; 
	cout<<ans+an<<'\n';
	return;
}
int32_t main(){
//	freopen("wxyt3.in","r",stdin);
//	freopen("my.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q>>W;
	up(i,1,n) cin>>a[i];
	bit.build(1,1,n);
	Log[0]=0;
	up(i,1,60){
		Log[i]=Log[i-1]+(1ll<<(i-1));
	}
	up(i,1,q){
		::sol();
	}
	return 0;
}