二分线段树求调60pts TLE

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
long long n, q, w, l, r, d, lk1;
long long ans[N*4 + 5], tag[N*4 + 5], a[N + 5]; 
inline void read(register long long &x)
{
	x = 0;
	register char v = getchar();
	while(v < '0' || v > '9') v = getchar();
	while(v >= '0' && v <= '9')
	x = (x << 3) + (x << 1) + (v & 15), v = getchar();
}
inline void write(register long long x)
{
	if(x < 10) putchar(x | 48);
	else write(x / 10), putchar(x % 10 | 48);
}
inline int ls(int x)
{
	return x << 1;
}
inline int rs(int x)
{
	return x << 1 | 1;
}
inline void pushup(int p)
{
	ans[p] = ans[ls(p)] + ans[rs(p)]; 
}
inline void pushdown(int p, int s, int t)
{
	int mid = (s + t) >> 1;
	if(tag[p])
	{
		ans[ls(p)] += (mid - s + 1) * tag[p], tag[ls(p)] += tag[p];
		ans[rs(p)] += (t - mid) * tag[p], tag[rs(p)] += tag[p];
		tag[p] = 0;
	}
}
inline void build(int p, int s, int t)
{
	if(s == t)
	{
		ans[p] = a[s];
		return;
	}
	int mid = (s + t) >> 1;
	build(ls(p), s, mid), build(rs(p), mid + 1, t);
	pushup(p); 
}
inline void update(int p, int s, int t, int l, int r, long long k)
{
	if(l <= s && t <= r)
	{
		ans[p] += (t - s + 1) * k;
		tag[p] += k;
		return;
	}
	int mid = (s + t) >> 1;
	pushdown(p, s, t);
	if(l <= mid) update(ls(p), s, mid, l, r, k);
	if(mid < r) update(rs(p), mid + 1, t, l, r, k);
	pushup(p);
}
inline long long query(int p, int s, int t, int l, int r)
{
	if(l <= s && t <= r) return ans[p];
	int mid = (s + t) >> 1;
	pushdown(p, s, t);
	long long sum = 0;
	if(l <= mid) sum = query(ls(p), s, mid, l, r);
	if(mid < r) sum += query(rs(p), mid + 1, t, l, r);
	return sum; 
}
inline long long fdl(long long a, int b)
{
	return a / b + (a % b != 0);
}
inline long long fdm(long long a, int b)
{
	if(a % b == 0) return b;
	return a % b;
}
inline long long calc(long long x, long long zd)
{
	//1 2^0 + 2^(x-1)
	//1 0
	//2 2^0
	//3 2^0 + 2^1
	long long tp = (1ll << (fdl(x, n) - 1)) - 1;
	return tp * zd + (1ll << (fdl(x, n) - 1)) * query(1, 1, n, 1, fdm(x, n)); 
}
inline long long calc2(long long x, long long step)
{
	return (1ll << step) * query(1, 1, n, 1, x);
}
int main(void)
{
//	freopen("wxyt4.in", "r", stdin);
//	freopen("t1.out", "w", stdout);
	read(n), read(q), read(w);
	for(register int i = 1; i <= n; ++ i)
	{
		read(a[i]);
	}
	build(1, 1, n);
	lk1 = log2(w / query(1, 1, n, 1, n) + 1) + 4;
	for(register int i = 1; i <= q; ++ i)
	{
		read(l), read(r), read(d);
		update(1, 1, n, l, r, d);
		long long tp = query(1, 1, n, 1, n);
		long long ll = 1, rr = lk1;
		while(ll < rr)
		{
			long long mid = (ll + rr) >> 1;
			if(calc(mid * n, tp) < w) ll = mid + 1;
			else rr = mid;
		}
		-- ll;
		long long sum = ((1ll << ll) - 1) * tp;
		long long lll = 1, rrr = n;
		while(lll < rrr)
		{
			long long mid = (lll + rrr) >> 1;
			if(sum + calc2(mid, ll) < w) lll = mid + 1;
			else rrr = mid;
		}
		lk1 = ll + 1;
		write(ll * n + lll - 1);
		putchar('\n');
	}
	return 0;
}