[主席树]HDOJ4348 To the moon

题意：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
", 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
", query(T[rt], l, r, 1, n));
103             }
104             else
105                 scanf("%d", &time);
106         }
107     }
108     return 0;
109 }

HDOJ 4348