线段树+二分 TLE#11~14 不解啊

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ls rt<<1
#define rs rt<<1|1
const int N=2e5+1;
int n,q,ans,a[N];
LL w,tree[N<<2],tag[N<<2];
void push_down(int rt,int l,int r){
	int mid=l+r>>1;
	tree[ls]+=tag[rt]*(mid-l+1);
	tree[rs]+=tag[rt]*(r-mid);
	tag[ls]+=tag[rt];
	tag[rs]+=tag[rt];
	tag[rt]=0;
	return;
}
void build(int rt,int l,int r){
	if(l==r){
		tree[rt]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tree[rt]=tree[ls]+tree[rs];
	return;
}
void upd(int rt,int l,int r,int L,int R,int v){
	if(L<=l&&r<=R){
		tree[rt]+=(r-l+1)*v;
		tag[rt]+=v;
		return;
	} 
	push_down(rt,l,r);
	int mid=l+r>>1;
	if(L<=mid) upd(ls,l,mid,L,R,v);
	if(R>mid) upd(rs,mid+1,r,L,R,v); 
	tree[rt]=tree[ls]+tree[rs];
	return;
}
int dfs(int rt,int l,int r,LL now,int p){
	if(l==r) return l;
	push_down(rt,l,r);
	int mid=l+r>>1;
	if(tree[ls]*p>=now) return dfs(ls,l,mid,now,p);
	return dfs(rs,mid+1,r,now-(tree[ls]*p),p);
}
int main(){
	scanf("%d %d %lld",&n,&q,&w);
	LL tot=0,now,ans;
	int l,r,d,p;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		tot+=a[i];
	}
	build(1,1,n);
	while(q--){
		scanf("%d %d %d",&l,&r,&d);
		upd(1,1,n,l,r,d);
		tot+=(r-l+1)*d;
		now=w,ans=0,p=1;
		while(now>tot*p){
			now=now-(tot*p);
			p<<=1;
			ans+=n;
		}
		printf("%lld\n",ans+dfs(1,1,n,now,p)-1);
	}
	return 0;
}