主要调 WA on #11 #12.

主要思路：树上二分斩杀一轮的死亡点

#include <bits/stdc++.h>
#define mid (l+r)/2
#define int long long
using namespace std;
int n,q,w,x,y,k,a[200005],sum[800005],lazy[800005],all,w2,cnt;
void push_up(int id){
	sum[id]=sum[id*2]+sum[id*2+1];
}
void push_down(int id,int l,int r){
	lazy[id*2]+=lazy[id];
	lazy[id*2+1]+=lazy[id];
	sum[id*2]+=(mid-l+1)*lazy[id];
	sum[id*2+1]+=(r-mid)*lazy[id];
	lazy[id]=0;
}
void build(int id,int l,int r){
	if (l==r){
		sum[id]=a[l];
		return;
	}
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	push_up(id); 
}
void update(int id,int l,int r,int x,int y,int w){
	if (x<=l&&r<=y){
		lazy[id]+=w;
		sum[id]+=w*(r-l+1);
		return;
	}
	push_down(id,l,r);
	if (x<=mid) update(id*2,l,mid,x,y,w);
	if (y>mid) update(id*2+1,mid+1,r,x,y,w);
	push_up(id);
}
int query(int id,int l,int r,int x,int y){
	if (x<=l&&r<=y) return sum[id];
	push_down(id,l,r);
	int ans = 0;
	if (x<=mid) ans += query(id*2,l,mid,x,y);
	if (y>mid) ans += query(id*2+1,mid+1,r,x,y);
	push_up(id);
	return ans;
}
void init(){
	cnt = 0,w2=w;
	scanf("%lld%lld%lld",&x,&y,&k);
	update(1,1,n,x,y,k);
	all = query(1,1,n,1,n);
}
void prpr(){
	while (w2 > all){
		w2-=all;
		cnt++;
		all*=2;
	}cnt *=n;
}
void find(){
	if (w2 < query(1,1,n,1,1)) return;
	if (w2 == all){
		cnt += n-1;
		return;
	}	
	int l=1,r=n,t=1<<(cnt/n);
	while (l < r-1){
		if (query(1,1,n,1,mid)*t<w2) l=mid;
		else r=mid;
	}cnt +=l;
}
signed main(){
	scanf("%lld%lld%lld",&n,&q,&w);
	for (int i = 1;i <= n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while (q--){
		init();prpr();
		find();
		printf("%lld\n",cnt);
	}
	return 0;
}