时隔半年，一雪前耻。
首先离线下来，考虑扫描线：从左往右扫，对于询问 \((x, l, r)\)，在 \(l\) 处加入 \(x\), 再 \(r\) 处统计答案。我们需维护当前所有需要操作的 \(x\) 的集，支持快速进行修改操作。
发现修改操作的实质是：对于所有 \(\le \lfloor\frac{a_i}{2}\rfloor\) 的 \(x\)，乘 \(-1\) 再加 \(a_i\)。容易想到使用平衡树维护，但在加上 \(a_i\) 后，原来 \(\le \lfloor\frac{a_i}{2}\rfloor\) 的 \(x\) 可能不再满足该性质，有可能与原来 \(\gt \lfloor\frac{a_i}{2}\rfloor\) 的部分有交，使用平衡树有交合并维护即可。
考虑如何处理有交合并时相等的节点 \(u, v\)：用并查集将 \(v\) 挂到 \(u\) 上，将 \(v\) 的信息合并到 \(u\) 中并在平衡树中删除 \(v\)。对于每次插入，我们记录下对应的节点编号，查询时用并查集跳到现在它在平衡树中对应的节点即可。由于需要删除节点，需要在 pushup 中更新父亲。
时间复杂度 \(\mathcal O(n\log ^ 2 n)\)，瓶颈在平衡树有交合并。自认为实现良好，感觉有些题解代码很迷惑。
\(p.s.\) 应特别注意 \(a_i\) 为负数时向下取整的写法：
cout << (-5 / 2) << endl; // 输出：-2
cout << (-5 >> 1) << endl; // 输出：-3
// godmoo's code
#include <bits/stdc++.h>
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define lbd lower_bound
#define ubd upper_bound
#define mathmod(a) (((a) % MOD + MOD) % MOD)
#define mem(a, b) memset(a, b, sizeof(a))
#define cpy(a, b) memcpy(a, b, sizeof(b))
#define ckmx(a, b) (a = max(a, b))
#define ckmn(a, b) (a = min(a, b))
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, int> pli;
const int N = 2e5 + 5;
int n, q, nod[N]; ll a[N], ans[N];
vector<pli> Add[N], Del[N];namespace FHQ {int tot, rt, l[N], r[N], fa[N], cnt[N], siz[N], pri[N]; ll val[N], mul[N], add[N];mt19937 rnd(343813);int f[N]; int find(int u){ return u == f[u] ? u : f[u] = find(f[u]); } // dsu 处理相等节点int create(ll x){tot++, cnt[tot] = siz[tot] = 1, pri[tot] = rnd();val[tot] = x, mul[tot] = 1;return f[tot] = tot;}void pushup(int u){siz[u] = siz[l[u]] + siz[r[u]] + cnt[u];if(l[u]) fa[l[u]] = u; // 重算 faif(r[u]) fa[r[u]] = u;}void pushmul(int u){ if(u) val[u] = -val[u], add[u] = -add[u], mul[u] = -mul[u]; }void pushadd(int u, ll x){ if(u) val[u] += x, add[u] += x; }void pushdown(int u){if(mul[u] != 1) pushmul(l[u]), pushmul(r[u]), swap(l[u], r[u]), mul[u] = 1;if(add[u]) pushadd(l[u], add[u]), pushadd(r[u], add[u]), add[u] = 0;}void split(int u, ll x, int& a, int& b){if(!u) return a = b = 0, void(); pushdown(u);if(val[u] <= x) a = u, split(r[u], x, r[a], b);else b = u, split(l[u], x, a, l[b]);pushup(u);}int merge(int u, int v){if(!u || !v) return u | v;if(pri[u] <= pri[v]) return pushdown(u), r[u] = merge(r[u], v), pushup(u), u;else return pushdown(v), l[v] = merge(u, l[v]), pushup(v), v;}int join(int u, int v){ // 有交合并if(!u || !v) return u | v;if(pri[u] > pri[v]) swap(u, v); pushdown(u), pushdown(v);int a, b, c; split(v, val[u], a, b), split(a, val[u] - 1, a, c);if(c) cnt[u] += cnt[v], f[c] = u;l[u] = join(l[u], a), r[u] = join(r[u], b);return pushup(u), u;}int ins(ll x){int a, b, c; split(rt, x, a, b), split(a, x - 1, a, c);c ? (cnt[c]++, siz[c]++) : c = create(x);return rt = merge(merge(a, c), b), c;}void access(int u){ if(fa[u]) access(fa[u]); return pushdown(u); }ll query(int u){ return u = find(u), access(u), val[u]; } // 平衡树上已重算 fa，找到原节点直接往上跳void upd(ll x){int a, b; split(rt, x >> 1ll, a, b);pushmul(a), pushadd(a, x);rt = join(a, b);}
} using namespace FHQ;int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> q;for(int i = 1; i <= n; i++) cin >> a[i];for(ll i = 1, x, l, r; i <= q; i++){cin >> x >> l >> r;Add[l].eb(x, i), Del[r].eb(x, i);}for(int i = 1; i <= n; i++){for(auto [x, id] : Add[i]) nod[id] = ins(x);upd(a[i]);for(auto [x, id] : Del[i]) ans[id] = query(nod[id]);}for(int i = 1; i <= q; i++) cout << ans[i] << '\n';cout << flush;return 0;
}