题意：n个数， m个操作
1. C l r d 给[l, r]区间的每个数加上d
2. Q l r: 查询[l, r]区间的和3. H l r t: 查询第t个操作时[l, r]区间的和4. B t: 回到第t个操作之后
因为有查询历史的区间和，故用主席树(保留了历史)
区间更新直接更新到每个子节点即可
神么链接都打不开
1 #define lson l, m 2 #define rson m+1, r 3 4 const int N=1e5+5; 5 const double eps=1e-8; 6 int L[N<<5], R[N<<5], sum[N<<5]; 7 LL ans[N<<5]; 8 int tot; 9 int a[N], T[N], Hash[N]; 10 11 void pushup(int rt) 12 { 13 ans[rt]=ans[L[rt]]+ans[R[rt]]; 14 } 15 16 int build(int l, int r) 17 { 18 int rt=(++tot); 19 sum[rt]=0; 20 if(l==r) 21 { 22 scanf("%I64d", &ans[rt]); 23 L[rt]=R[rt]=0; 24 return rt; 25 } 26 int m=(l+r)>>1; 27 L[rt]=build(lson); 28 R[rt]=build(rson); 29 pushup(rt); 30 return rt; 31 } 32 33 int update(int pre, int _L, int _R, int l, int r, LL x) 34 { 35 int rt=(++tot); 36 L[rt]=L[pre], R[rt]=R[pre], sum[rt]=sum[pre], ans[rt]=ans[pre]+x*(_R-_L+1); 37 if(_L<=l && r<=_R) 38 { 39 sum[rt]+=x; 40 return rt; 41 } 42 int m=(l+r)>>1; 43 if(_R<=m) 44 L[rt]=update(L[pre], _L, _R, lson, x); 45 else if(_L>m) 46 R[rt]=update(R[pre], _L, _R, rson, x); 47 else 48 { 49 L[rt]=update(L[rt], _L, m, lson, x); 50 R[rt]=update(R[rt], m+1, _R, rson, x); 51 } 52 return rt; 53 } 54 55 LL query(int rt, int _L, int _R, int l, int r) 56 { 57 LL cnt=sum[rt]*(LL)(_R-_L+1); 58 if(_L<=l && r<=_R) 59 return ans[rt]; 60 int m=(l+r)>>1; 61 if(_R<=m) 62 cnt+=query(L[rt], _L, _R, lson); 63 else if(_L>m) 64 cnt+=query(R[rt], _L, _R, rson); 65 else 66 { 67 cnt+=query(L[rt], _L, m, lson); 68 cnt+=query(R[rt], m+1, _R, rson); 69 } 70 return cnt; 71 } 72 73 int main() 74 { 75 int n, m; 76 while(~scanf("%d%d", &n, &m)) 77 { 78 tot=0; 79 T[0]=build(1, n); 80 int time=0; 81 while(m--) 82 { 83 char op[5]; 84 scanf("%s", op); 85 if(op[0]=='Q') 86 { 87 int l, r; 88 scanf("%d%d", &l, &r); 89 printf("%I64d\n", query(T[time], l, r, 1, n)); 90 } 91 else if(op[0]=='C') 92 { 93 int l, r; 94 LL x; 95 scanf("%d%d%I64d", &l, &r, &x); 96 T[time+1]=update(T[time++], l, r, 1, n, x); 97 } 98 else if(op[0]=='H') 99 {100 int l, r, rt;101 scanf("%d%d%d", &l, &r, &rt);102 printf("%I64d\n", query(T[rt], l, r, 1, n));103 }104 else105 scanf("%d", &time);106 }107 }108 return 0;109 }