我现在写了一个 $\Theta(Q\log^2 n)$ 的复杂度代码，请问还有救吗？是不是需要换一个思路？

就是直接根据题意线段树 + 二分。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
int n, q, W, a[N];
struct Node {
	int l, r;
	int sum, tag;
}tr[N << 2];
void pushup(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
	if (!tr[u].tag) return;
	tr[u << 1].tag += tr[u].tag, tr[u << 1 | 1].tag += tr[u].tag;
	tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].tag;
	tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].tag;
	tr[u].tag = 0;
}
void build(int u, int l, int r) {
	tr[u].l = l, tr[u].r = r;
	if (l == r) {
		tr[u].sum = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}
void modify(int u, int l, int r, int d) {
	if (l <= tr[u].l && tr[u].r <= r) {
		tr[u].tag += d;
		tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
		return;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid) modify(u << 1, l, r, d);
	if (r > mid) modify(u << 1 | 1, l, r, d);
	pushup(u); 
}
int query(int u, int l, int r) {
	if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1, res = 0;
	if (l <= mid) res += query(u << 1, l, r);
	if (r > mid) res += query(u << 1 | 1, l, r);
	return res; 
}

int work() {
	int allsum = tr[1].sum;
	//cout<<allsum<<endl;
	int big = 1, mul2 = 1, cur = 0;
	for (; ; big ++ ) {
		cur += mul2 * allsum;
		if (cur >= W) {
			cur -= mul2 * allsum;
			big -- ;
			break;
		}
		mul2 *= 2;
	} 
	//cout<<"W, big, cur: "<<W<<" "<<big<<" "<<cur<<endl<<"Queries: "; 
	//for (int i=1;i<=n;i++) cout<<(query(1,1,i)*mul2)<<" "; cout<<endl;
	int small = 0, l = 1, r = n;
	while (l <= r) {
		int mid = l + r >> 1;
		if (query(1, 1, mid) * mul2 < W-cur) small = mid, l = mid + 1;
		else r = mid - 1;
	}
	//cout << big << " " << small << endl;
	return big * n + small;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q >> W;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	build(1, 1, n);
	while (q -- ) {
		int l, r, d;
		cin >> l >> r >> d;
		modify(1, l, r, d);
		cout << work() << "\n";
	}
	return 0;
}