线段树上二分60ptsTLE求优化

#include<iostream>
#include<algorithm>
#include<cmath>
const int N = 2e5 + 5;
int n, q;
long long w, a[N], sum, p[74] = {0, 1}, tr[N<<2], tag[N<<2], t[74] = {1};
void build(int p, int l, int r) {
	if(l == r) {
		tr[p] = a[l];
		return;
	}
	int mid = (l+r) >> 1;
	build(p*2, l, mid), build(p*2+1, mid+1, r);
	tr[p] = tr[p*2] + tr[p*2+1];
}
void push_down(int p, int l, int r) {
	int mid = (l+r) >> 1;
	tr[p*2] += tag[p]*(mid-l+1);
	tr[p*2+1] += tag[p]*(r-mid);
	tag[p*2] += tag[p], tag[p*2+1] += tag[p];
	tag[p] = 0; 
}
void update(int p, int l, int r, int nl, int nr, int k) {
	if(l>nr || r<nl) return; 
	if(nl<=l && r<=nr) {
		tr[p] += k*(r-l+1);
		tag[p] += k;
		return;
	}
	push_down(p, l, r);
	int mid = (l+r) >> 1;
	if(l <= mid) update(p*2, l, mid, nl, nr, k);
	if(r > mid) update(p*2+1, mid+1, r, nl, nr, k);
	tr[p] = tr[p*2] + tr[p*2+1];
}
long long query(int p, int l, int r, int nl, int nr) {
	if(l>nr || r<nl) return 0; 
	if(nl<=l && r<=nr) return tr[p];
	push_down(p, l, r);
	int mid = (l+r) >> 1;
	long long sum = 0;
	if(l <= mid) sum += query(p*2, l, mid, nl, nr);
	if(r > mid) sum += query(p*2+1, mid+1, r, nl, nr);
	return sum;
}
long long solve(long long x) {
	int lun = std::lower_bound(p, p+63, ceil(1.*x/sum))-p;
	long long ans = n*(lun-1);
	x -= p[lun-1]*sum;
	int l = 1, r = n, pos;
	while(l <= r) {
		int mid = (l+r) >> 1;
		if(t[lun-1]*query(1, 1, n, 1, mid) >= x) {
			pos = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	ans += pos-1;
	return ans;
}
inline long long read()
{
   
    int X = 0, w = 0; char ch = 0;
    while (!isdigit(ch)) {
    w |= ch == '-'; ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
int main () {
	for(int i = 1;i <= 63;++i) t[i] = t[i-1]*2;
	for(int i = 2;i <= 63;++i) p[i] = 2*p[i-1]+1;
	scanf("%d%d%lld", &n, &q, &w);
	for(int i = 1;i <= n;++i) scanf("%lld", a+i), sum += a[i];
	build(1, 1, n);
	while(q--) {
		int l, r, d;
		l = read(), r = read(), d = read();
		sum += (r-l+1)*d;
		update(1, 1, n, l, r, d);
		printf("%lld\n", solve(w));
	}
	return 0;
}