题目描述
给定一段长度为 (N) 的序列 (a) 以及 (M) 次操作，操作有以下几种：
C l r d：将区间 ([l,r]) 中的数都加上 (d)Q l r：查询当前时间戳区间 ([l,r]) 中所有数的和H l r t：查询时间戳为 (t) 时，区间 ([l,r]) 中所有数的和B t：将当前时间戳重置为 (t)
对于每一次询问操作，输出一行对应的答案。
时间戳初始值为 (0)
数据范围：
(1leq N,Mleq 10^5)
然后要开 long long
基本思路
主席树的一道比较模板的题。。。
原谅我不想讲细节（其实代码里面写的还可以）
关于标记永久化的一些实现细节，我是参考的《信息学奥赛一本通 (cdot) 提高篇》
细节注意事项
long long一定要开- 细节不要写挂，数据结构题还是有点难调的
- 应该不会有人像我一样搞错输入顺序吧。。。
参考代码
/*--------------------------------
Author: The Ace Bee
Blog: www.cnblogs.com/zsbzsb
This code is made by The Ace Bee
--------------------------------*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
typedef long long LL;
const int _ = 100010;
int n, m, a[_];
int tot, rt[_], lc[_ << 5], rc[_ << 5];
LL sum[_ << 5], add[_ << 5];
inline void build(int& p, int l = 1, int r = n) {
p = ++tot;
if (l == r) return read(sum[p]);
int mid = (l + r) >> 1;
build(lc[p], l, mid), build(rc[p], mid + 1, r);
sum[p] = sum[lc[p]] + sum[rc[p]];
}
inline void update(int& p, int q, int ql, int qr, int v, int l = 1, int r = n) {
lc[p = ++tot] = lc[q], rc[p] = rc[q], add[p] = add[q], sum[p] = sum[q];
if (ql <= l && r <= qr) { add[p] += v; return; }
int mid = (l + r) >> 1;
if (ql <= mid) update(lc[p], lc[q], ql, qr, v, l, mid);
if (qr > mid) update(rc[p], rc[q], ql, qr, v, mid + 1, r);
sum[p] += 1ll * v * (min(qr, r) - max(ql, l) + 1);
}
inline LL query(int p, int ql, int qr, int l = 1, int r = n) {
if (ql <= l && r <= qr) return sum[p] + 1ll * add[p] * (r - l + 1);
int mid = (l + r) >> 1; LL res = 0;
if (ql <= mid) res += query(lc[p], ql, qr, l, mid);
if (qr > mid) res += query(rc[p], ql, qr, mid + 1, r);
return res + 1ll * add[p] * (min(qr, r) - max(ql, l) + 1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m), build(rt[0]);
int tim = 0;
for (rg int i = 1; i <= m; ++i) {
char s[5]; scanf("%s", s);
if (s[0] == 'B') read(tim), tot = rt[tim + 1] - 1;
else if (s[0] == 'C') { int ql, qr, v;
read(ql), read(qr), read(v), ++tim;
update(rt[tim], rt[tim - 1], ql, qr, v);
} else if (s[0] == 'Q') { int ql, qr;
read(ql), read(qr);
printf("%lld
", query(rt[tim], ql, qr));
} else if (s[0] == 'H') { int t, ql, qr;
read(ql), read(qr), read(t);
printf("%lld
", query(rt[t], ql, qr));
}
}
return 0;
}