wa on #13线段树二分 求调

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll read() {
	ll n=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9') {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') {
		n=(n<<1)+(n<<3)+ch-'0';
		ch=getchar();
	}
	return f==1?n:-n;
}

void write(ll x) {
	if(x<0) {
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar((x%10)+'0');
}

const int N=2e5+7;

int n,q;
ll w;
ll a[N];

void input() {
	n=read(),q=read(),w=read();
	for(int i=1;i<=n;i++) 
		a[i]=read();
}

ll p[N];

struct Tr{
	int l,r,mid;
	ll sum;
	ll add;
}tr[N<<2];

void pushup(int u) {
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u) {
	Tr &f=tr[u],&ls=tr[u<<1],&rs=tr[u<<1|1];
	if(f.add) {
		ls.sum+=(ls.r-ls.l+1)*f.add;
		ls.add+=f.add;
		rs.sum+=(rs.r-rs.l+1)*f.add;
		rs.add+=f.add; 
		f.add=0;
	}
}

void build(int u,int l,int r) {
	tr[u].l=l,tr[u].r=r,tr[u].mid=(l+r)>>1;
	if(l==r) {
		tr[u].sum=a[l];
		return;
	}
	build(u<<1,l,tr[u].mid);
	build(u<<1|1,tr[u].mid+1,r);
	pushup(u);
}

void modify(int u,int l,int r,int ql,int qr,ll k) {
	if(ql<=l && qr>=r) {
		tr[u].sum+=(r-l+1)*k;
		tr[u].add+=k;
		return;
	}
	pushdown(u);
	if(ql<=tr[u].mid) modify(u<<1,l,tr[u].mid,ql,qr,k);
	if(qr>tr[u].mid) modify(u<<1|1,tr[u].mid+1,r,ql,qr,k);
	pushup(u);
}

ll calc(int u,int l,int r,ll mul,ll s) {
	if((tr[u].sum<<mul)<s) return r;
	if(l==r) return -1;
	pushdown(u);
	int mid=(l+r)>>1;
	if((tr[u<<1].sum<<mul)<s) {
		return max((ll)mid,calc(u<<1|1,mid+1,r,mul,s-(tr[u<<1].sum<<mul)));
	}else{
		return calc(u<<1,l,mid,mul,s);
	}
}

void work() {
	p[0]=1;
	for(int i=1;i<N;i++) {
		p[i]=p[i-1]*2;
		if(p[i]>w) break;
	}
	build(1,1,n);
	ll sum=0;
	for(int i=1;i<=n;i++) 
		sum+=a[i];
	while(q--) {
		int l,r;
		ll d;
		l=read(),r=read(),d=read();
		modify(1,1,n,l,r,d);
		sum+=(r-l+1)*d;
		ll t=(w%sum==0)?(w/sum):(w/sum+1);
		ll k=log2(t);
		ll t2=p[k]-1;
		ll rest=w-t2*sum;
		ll v=calc(1,1,n,k,rest);
		ll ans=k*n+v;
		write(ans),putchar('\n');
	}
}

int main() {
	input();
	work();
	return 0;
}