首先考虑暴力的贪心。
从 \(r\) 到 \(l\) 依次遍历，若 \(a_i < x\) 则一直进行题目中的操作。
正确性是能保证的，因为选后面的 \(j\) 只能 \(+ 1\)，而选 \(i\) 可以 \(+2\)，且 \(i\) 前面的部分都是 \(+1\)。
考虑转化一下，把对 \(i\) 进行操作 \(k\) 次后，\(\forall j\in [1, i), a_j\leftarrow a_j + k\) 改为 \(x\leftarrow x - k\)。
可以发现这样肯定是不会影响答案的，而且这样就可以直接维护 \(x\) 的值了。
考虑用 \(f(i, x)\) 表示现在在 \(a_i\) 和 \(x\) 的值时满足 \([1, i]\) 都能满足题目所述的条件时的答案。
若 \(a_i\ge x\)，则 \(f(i, x) = f(i - 1, x)\)；否则 \(f(i, x) = i\times \lceil\frac{x - a_i}{2}\rceil + f(i - 1, \lfloor\frac{x + a_i}{2}\rfloor)\)。
考虑询问 \((l, r, x)\)，那因为只需要满足 \([l, r]\) 就行了，就不需要满足 \([1, l)\)。
就找到 \(f(r, x)\) 递归到 \(i = l - 1\) 时的 \(x'\)，\(f(r, x) - f(l - 1, x')\) 就是答案。
能够发现 \(f\) 的转移式子是一棵树，便考虑把这棵树建出来，就可以通过在到根的链上二分到对应的时间点。
优化一下，用个树剖就行了。
考虑对于 \(a_i\ge x\) 的节点，这个节点其实不会产生贡献，不如直接等到 \(j < i, a_j < x\) 时再建点。
优化完这个节点数就只有 \(O(q\log W)\)（\(W\) 是值域）了。
考虑 \(f(i, x_1), f(i, x_2), x_1 < x_2\)，那么每走一步，\(x2 - x1\) 都会缩小一半，所以至多在 \(\log W\) 次后就会成为一个节点。
然后用个数据结构维护建树即可，注意常数。
时间复杂度 \(O(n\log q + q\log W\log q + q\log (q\log W))\)。
#include<bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int, int>;
const int maxn = 3e5 + 10, maxp = maxn * 33;
int fa[maxp], ti[maxp], siz[maxp], son[maxp], top[maxp]; i64 sum[maxp]; int m;
std::vector<pii> es[maxp];
int a[maxn];
int ql[maxn], qr[maxn], qx[maxn], id[maxn];
std::vector<pii> inx[maxn];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int q; scanf("%d", &q);
for (int i = 1; i <= q; i++) scanf("%d%d%d", &ql[i], &qr[i], &qx[i]);
for (int i = 1; i <= q; i++) inx[qr[i]].emplace_back(qx[i], i);
std::priority_queue<pii> s; std::vector<pii> t;
for (int i = n; i; i--) {
for (pii j : inx[i]) s.emplace(j.first, id[j.second] = ++m);
while (! s.empty() && s.top().first > a[i]) {
int x = s.top().first, u = s.top().second; s.pop();
int v = (x + a[i]) >> 1;
if (t.empty() || t.back().first != v) t.emplace_back(v, ++m);
fa[u] = t.back().second, sum[u] = 1ll * i * ((x + 1 - a[i]) >> 1), ti[u] = i;
}
while (! t.empty()) s.push(t.back()), t.pop_back();
}
m++, ti[m] = -1;
while (! s.empty()) fa[s.top().second] = m, ti[s.top().second] = 0, s.pop();
for (int i = m - 1; i; i--) sum[i] += sum[fa[i]];
for (int i = 1; i < m; i++) siz[i]++, siz[fa[i]] += siz[i];
for (int i = 1; i <= m; i++) siz[i] > siz[son[fa[i]]] && (son[fa[i]] = i);
top[m] = m;
for (int i = m - 1; i; i--) top[i] = i == son[fa[i]] ? top[fa[i]] : i;
for (int i = m; i; i--) es[top[i]].emplace_back(ti[i], i);
for (int i = 1; i <= q; i++) {
int u = top[id[i]];
while (ti[u] >= ql[i]) u = top[fa[u]];
int w = std::lower_bound(es[u].begin(), es[u].end(), (pii){ql[i], 0}) - es[u].begin() - 1;
printf("%lld\n", sum[id[i]] - sum[es[u][w].second]);
}
return 0;
}