如题，是标记永久化的可持久化线段树。太晚了，先挂一个求助帖。

测评记录：https://www.luogu.com.cn/record/106247033

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
	typedef long long LL;
	const int N = 1e6 + 5;
	LL n, q, l, r, x, t, a[N], T[N];
	char opt;
	struct SegmentTree {
	    LL cnt, sum[N << 1], tag[N << 1], Ls[N << 1], Rs[N << 1];
	    int modify(int p, int l, int r, int nl, int nr, LL k) {
	    	LL len = min(nr, r) - max(nl, l) + 1;
	    	int rt = ++ cnt, mid = (l + r) >> 1;
	    	Ls[rt] = Ls[p], Rs[rt] = Rs[p], sum[rt] = sum[p] + k * len;
	        if (nl <= l && r <= nr) { tag[rt] += k; return rt; }
	        if (nl <= mid) Ls[rt] = modify(Ls[p], l, mid, nl, nr, k);
	        if (nr > mid) Rs[rt] = modify(Rs[p], mid + 1, r, nl, nr, k);
	        return rt;
	    }
	    LL query(int p, int l, int r, int nl, int nr) {
	    	LL len = min(nr, r) - max(nl, l) + 1;
			LL mid = (l + r) >> 1, res = tag[p] * len;
	        if (nl <= l && r <= nr) return sum[p];
	        if (nl <= mid) res += query(Ls[p], l, mid, nl, nr);
	        if (nr > mid) res += query(Rs[p], mid + 1, r, nl, nr);
	        return res;
	    }
	   	int build(int l, int r, LL* a) {
	   		int rt = ++ cnt, mid = (l + r) >> 1;
			if (l == r) { sum[rt] = a[l]; return rt; }
			Ls[rt] = build(l, mid, a), Rs[rt] = build(mid + 1, r, a);
			sum[rt] = sum[Ls[rt]] + sum[Rs[rt]];
			return rt; 
		}
	    SegmentTree() { cnt = 1; }
	    void print() {
	        for (int i = 1; i <= n; i ++)
	            cout << query(1, 1, n, i, i) << ' ';
	        cout << '\n';
	    }
	} Sgt;
	int main() {
		cin >> n >> q;
		for (int i = 1; i <= n; i ++)
			cin >> a[i];
		T[0] = Sgt.build(1, n, a);
		for (int i = 1; i <= q; i ++) {
			cin >> opt;
			if (opt == 'C') {
				cin >> l >> r >> x, t ++;
				T[t] = Sgt.modify(T[t - 1], 1, n, l, r, x);
			}
			if (opt == 'Q') cin >> l >> r, cout << Sgt.query(T[t], 1, n, l, r) << '\n';
			if (opt == 'H') cin >> l >> r >> x, cout << Sgt.query(T[x], 1, n, l, r) << '\n';
			if (opt == 'B') cin >> x, t = x;
		}
		return 0;
	}
}
int main() {
	return Milkcat::main();
}