caioj 1447
题意：维护区间和，有区间增加，要求可持久化 (回退、查询某个版本)
每个询问开一棵线段树，回退直接删掉中间的线段树即可。由于是主席树不能pushdown，pushup，所以增加的时候直接更新sumv的值，查询时lazy值直接累加乘以查询区间长度即可，具体操作可以看代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 100000 + 5;
LL n, m, ai[MAXN], qzh[MAXN], rt[MAXN], now, sz;
#define M ((l + r) >> 1)
LL sumv[MAXN * 40], lc[MAXN * 40], rc[MAXN * 40], lazy[MAXN * 40];
int mge(LL &x, LL y) {
if (y == 0) return 0;
if (x == 0) return x = y, 0;
sumv[x] += sumv[y], lazy[x] += lazy[y];
mge(lc[x], lc[y]), mge(rc[x], rc[y]);
return 0;
}
void build(LL l, LL r, LL &x, LL cl, LL cr, LL v) {
if (x == 0) x = ++sz;
sumv[x] += (cr - cl + 1) * v;//直接加，免去pushup
if (l == cl && r == cr) {
lazy[x] += v;
return ;
}
if (cr <= M) build(l, M, lc[x], cl, cr, v); else if (cl > M) build(M + 1, r, rc[x], cl, cr, v);
else build(l, M, lc[x], cl, M, v), build(M + 1, r, rc[x], M + 1, cr, v);
//整个区间在左边、右边、分开两边
}
LL query(LL l, LL r, LL x, LL cl, LL cr, LL tmp) {
if (l == cl && r == cr) return (r - l + 1) * tmp + sumv[x];
if (cr <= M) return query(l, M, lc[x], cl, cr, tmp + lazy[x]);
else if (cl > M) return query(M + 1, r, rc[x], cl, cr, tmp + lazy[x]);
else return query(l, M, lc[x], cl, M, tmp + lazy[x]) + query(M + 1, r, rc[x], M + 1, cr, tmp + lazy[x]);
//整个查询区间在左边、右边、分开两边，和普通线段树不同，相当于用 M 分离查询区间
//直接累加lazy最后乘查询区间长度
}
void clean() {
now = sz = 0;
for (LL i = 0; i <= 100000 + 3; i++) rt[i] = qzh[i] = 0;
for (LL i = 0; i <= 4000000 + 3; i++) sumv[i] = lc[i] = rc[i] = lazy[i] = 0;
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &ai[i]), qzh[i] = qzh[i - 1] + ai[i];
for (LL i = 1; i <= m; i++) {
LL tp; scanf("%lld", &tp);
if (tp == 1) {
LL l, r, k; scanf("%lld%lld%lld", &l, &r, &k);
build(1, n, rt[++now], l, r, k), mge(rt[now], rt[now - 1]);
}
if (tp == 2) {
LL l, r; scanf("%lld%lld", &l, &r);
printf("%lld\n", qzh[r] - qzh[l - 1] + query(1, n, rt[now], l, r, 0));
}
if (tp == 3) {
LL l, r, h; scanf("%lld%lld%lld", &l, &r, &h);
printf("%lld\n", qzh[r] - qzh[l - 1] + query(1, n, rt[h], l, r, 0));
}
if (tp == 4) {
LL h; scanf("%lld", &h);
for (LL i = h + 1; i <= now; i++) rt[i] = 0;
now = h;
}
}
return 0;
}
int main() {
scanf("%lld%lld", &n, &m), solve();
return 0;
}
【题目描述】
给出一个长度为n（1<=n<=100000）的序列a[1],a[2],a[3]……,a[n]（1<=a[i]<=1000000000），有m个操作（1<=n<=100000）。
操作类型分为4种。
1 l r k：给l到r之间的数都加上k（1<=k<=1000）。
2 l r：询问当前l到r的和。
3 l r h：询问第h次修改（修改只指1操作）时l到r的和。
4 h：回到第h次修改的时候不再返回。
【输入数据】
第一行两个数n和m(n,m<=10^5)。
接下来一行n个数。
接下来m行m个操作。
【输出数据】
每行对应一个询问。
【输入样例】
10 5
1 2 3 4 5 6 7 8 9 10
2 4 4
2 1 10
2 2 4
1 3 6 3
2 2 4
【输出样例】
4
55
9
15
原样例太弱，补充一个样例
【输入样例】
5 10
1 2 3 4 5
2 2 4
1 1 2 3
2 2 4
1 2 4 100
2 2 4
3 2 4 1
3 2 4 2
4 1
1 2 4 10
2 2 4
【输出样例】
9
12
312
12
321
42
