线段树 70pts TLE 求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll n,q,W;
ll a[N],t[N<<2],lz[N<<2];
ll read(){
	ll res=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-')f*=-1;
		ch=getchar();
	}
	while ('0'<=ch&&ch<='9'){
		res=res*10+ch-'0';
		ch=getchar();
	}
	return res*f;
}
int ls(int o){return o<<1;}
int rs(int o){return o<<1|1;}
void push_up(int o){
	t[o]=t[ls(o)]+t[rs(o)];
}
void build(int s=1,int e=n,int o=1){
	if (s==e){
		t[o]=a[s];
		return;
	}
	int mid=(s+e)>>1;
	build(s,mid,ls(o));
	build(mid+1,e,rs(o));
	push_up(o);
}
void f(int s,int e,int o,int x){
	t[o]+=(e-s+1)*x;
	lz[o]+=x;
}
void push_down(int s,int e,int o){
	if (!lz[o])return;
	int mid=(s+e)>>1;
	f(s,mid,ls(o),lz[o]);
	f(mid+1,e,rs(o),lz[o]);
	lz[o]=0;
}
void update(int l,int r,int x,int s=1,int e=n,int o=1){
	if (l<=s&&e<=r){
		f(s,e,o,x);
		return;
	}
	int mid=(s+e)>>1;
	push_down(s,e,o);
	if (mid>=l)update(l,r,x,s,mid,ls(o));
	if (mid+1<=r)update(l,r,x,mid+1,e,rs(o));
	push_up(o);
}
ll query(int l,int r,int s=1,int e=n,int o=1){
	if (l<=s&&e<=r){
		return t[o];
	}
	int mid=(s+e)>>1;
	ll res=0;
	push_down(s,e,o);
	if (mid>=l)res+=query(l,r,s,mid,ls(o));
	if (mid+1<=r)res+=query(l,r,mid+1,e,rs(o));
	return res;
}
int find(ll lft,ll bst,int s=1,int e=n,int o=1){
	if (lft<=0||s==e)return e;
	//cerr<<s<<' '<<e<<'\n';
	int mid=(s+e)>>1;
	ll lval=query(s,mid)*bst;
	//cerr<<lval<<'\n';
	if (lval>=lft)return find(lft,bst,s,mid,ls(o));
	else return find(lft-lval,bst,mid+1,e,rs(o)); 
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	n=read(),q=read(),W=read();
	for (int i=1;i<=n;i++)a[i]=read();
	build();
	for (int i=1;i<=q;i++){
		int l,r,d;
		l=read(),r=read(),d=read();
		update(l,r,d);
		ll sum=query(1,n),tmp=W,rd=0,bst=1;
		while (tmp-sum>0){
			rd++;
			tmp-=sum;
			sum*=2;
			bst*=2;
		}
		cout<<rd*n+find(tmp,bst)-1<<'\n';
	}
	return 0;
}