题意:
给出一个长度为\(n(n \leq 10^5)\)的序列，最开始时间\(t=0\)，支持下面几个操作：
- \(C \, l \, r \, d\)：将区间\([l,r]\)每个数都加上\(d\)，并且时间\(t\)增加1秒
- \(Q \, l \, r\)：查询当前时间区间\([l,r]\)所有元素之和
- \(H \, l \, r \, t\)：查询时间为\(t\)时，区间\([l,r]\)的所有元素之和
- \(B \, t\)：时间回溯到\(t\)
输出每次查询的结果。
分析：
这是支持区间修改的可持久化线段树。
我们维护一个\(sum\)表示区间的元素和以及一个懒惰标记\(add\)。 由于是主席树，查询时如果要\(pushdown\)就会新增节点，空间开销比较大。 所以查询时不进行\(pushdown\)，而是累加所经过的节点的\(add\)值 乘上 查询区间长度。#include#include #include using namespace std;typedef long long LL;const int maxn = 100000 + 10;struct Node{ int lch, rch, add; LL sum;};int sz;Node T[maxn << 5];int n, m, root[maxn];LL S[maxn];char op[5];int update(int pre, int L, int R, int qL, int qR, int v) { int rt = ++sz; T[rt] = T[pre]; T[rt].sum += (LL)v * (min(R, qR) - max(L, qL) + 1); if(qL <= L && R <= qR) { T[rt].add += v; return rt; } int M = (L + R) / 2; if(qL <= M) T[rt].lch = update(T[pre].lch, L, M, qL, qR, v); if(qR > M) T[rt].rch = update(T[pre].rch, M+1, R, qL, qR, v); return rt;}LL query(int rt, int L, int R, int qL, int qR) { if(qL <= L && R <= qR) return T[rt].sum; LL ans = (LL)T[rt].add * (min(R, qR) - max(L, qL) + 1); int M = (L + R) / 2; if(qL <= M) ans += query(T[rt].lch, L, M, qL, qR); if(qR > M) ans += query(T[rt].rch, M+1, R, qL, qR); return ans;}int main(){ bool flag = false; while(scanf("%d%d", &n, &m) == 2) { if(flag) puts(""); flag = true; for(int i = 1; i <= n; i++) { scanf("%lld", S + i); S[i] += S[i - 1]; } sz = 0; int time = 0; while(m--) { scanf("%s", op); int l, r, d; scanf("%d", &l); if(op[0] == 'C') { scanf("%d%d", &r, &d); time++; root[time] = update(root[time - 1], 1, n, l, r, d); } else if(op[0] == 'Q') { scanf("%d", &r); LL ans = S[r] - S[l - 1]; ans += query(root[time], 1, n, l, r); printf("%lld\n", ans); } else if(op[0] == 'H') { scanf("%d%d", &r, &d); LL ans = S[r] - S[l - 1]; ans += query(root[d], 1, n, l, r); printf("%lld\n", ans); } else { time = l; } } } return 0;}