1 /*  2 ID:esxgx1  3 LANG:C++  4 PROG:hdu4348  5 */  6 #include <cassert>  7 #include <cstdio>  8 #include <cstring>  9 #include <iostream> 10 #include <algorithm> 11 using namespace std; 12  13 #define MAXM    200007 14 #define NN    10000007 15  16 int lsi[NN], rsi[NN], used; 17 long long tag[NN]; 18 long long v[NN]; 19  20 inline void clone(int t, int T) 21 { 22 //    assert(lsi[T] < used) ,assert(rsi[T] < used); 23     lsi[t] = lsi[T], rsi[t] = rsi[T]; 24     tag[t] = tag[T]; v[t] = v[T]; 25 } 26  27 #define pushdown(t)    if (tag[t] != 0) { 28     int nl, nr;  29     nl = used++, nr = used++;     30     clone(nl, lsi[t]), clone(nr, rsi[t]);     31     tag[nl] += tag[t]; tag[nr] += tag[t];     32     v[nl] += tag[t] * (m-l+1);     33     v[nr] += tag[t] * (r-m);     34     lsi[t] = nl, rsi[t] = nr, tag[t] = 0;     35 } 36  37  38  39 #define pushup(t)    v[t] = v[lsi[t]] + v[rsi[t]]; 40  41 int build(int l, int r) 42 { 43     int t = used++; 44     tag[t] = 0; 45     if (l == r) { 46         scanf("%I64d", &v[t]); 47         lsi[t] = rsi[t] = 0; 48     } else { 49         int m = (l+r) >> 1; 50         lsi[t] = build(l, m); 51         rsi[t] = build(m+1, r); 52         pushup(t) 53         // printf("====%d %d %d\n", l, r, v[t]); 54     } 55     return t; 56 } 57  58 int rshift(int L, int R, int d, int l, int r, int T) 59 { 60     int t = used++; 61 //    printf("=<>=%d %d %d\n", l, r, v[T]); 62     if (L<=l && r<=R) { 63         tag[t] = tag[T] + d; 64         lsi[t] = lsi[T], rsi[t] = rsi[T]; 65         v[t] = v[T] + d * (long long)(r-l+1); 66 //        printf(">--<%d %d %lld %lld\n", l, r, tag[t], v[t]); 67     } else { 68 //        assert(l<r); 69         int m = (l+r) >> 1; 70         clone(t, T); 71         pushdown(t) 72         if (L <= m) lsi[t] = rshift(L, R, d, l, m, lsi[t]); 73         if (m < R) rsi[t] = rshift(L, R, d, m+1, r, rsi[t]); 74         pushup(t) 75 //        printf("---<%d %d %lld %lld\n", l, r, v[t], tag[t]); 76  77     } 78     return t; 79 } 80  81  82 long long query(int L, int R, int l, int r, int T, long long tg) 83 { 84 //    printf("l %d r %d  %d 000\n", l, r, tag[T]); 85     if (L <= l && r <= R) return v[T] + tg * (r-l+1); 86     tg += tag[T]; 87     long long rslt = 0; 88     int m = (l+r) >> 1; 89     //pushdown(T) 90     if (L <= m) rslt += query(L, R, l, m, lsi[T], tg); 91     if (m < R) rslt += query(L, R, m+1, r, rsi[T], tg); 92 //    printf("l %d r %d %lld(%lld)\n", l, r, rslt, tag[T]); 93     return rslt; 94 } 95  96 /* 97 long long query(int L, int R, int l, int r, int T, long long tg) 98 { 99 //    printf("l %d r %d  %d 000\n", l, r, tag[T]);100     if (L <= l && r <= R) return v[T];101     long long rslt = 0;102     int m = (l+r) >> 1;103     pushdown(T)104     if (L <= m) rslt += query(L, R, l, m, lsi[T], tg);105     if (m < R) rslt += query(L, R, m+1, r, rsi[T], tg);106     pushup(T)107     printf("l %d r %d %lld (%lld)\n", l, r, rslt, tag[T]);108     return rslt;109 }*/110 111 112 int T[MAXM];113 114 int main(void)115 {116     #ifndef ONLINE_JUDGE117     freopen("in.txt", "r", stdin);118     #endif119 120     int N, M, Case = 0;121     while(scanf("%d%d", &N, &M) > 0) {122         if (Case++) putchar(‘\n‘);123         used = 1;124         int t = 0;125         T[0] = build(1, N);126         for(;M; --M) {127             char type[4];128             int L, R, D;129             scanf("\n%s%d", type, &L);130             switch(type[0]) {131                 case ‘Q‘:132                     scanf("%d", &R);133                     printf("%I64d\n", query(L, R, 1, N, T[t], 0));134                     break;135                 case ‘C‘:136                     scanf("%d%d", &R, &D);137                     T[t+1] = rshift(L, R, D, 1, N, T[t]);138                     // printf("t=%d %d\n", t+1, T[t+1]);139                     ++t;140                     break;141                 case ‘H‘:142                     scanf("%d%d", &R, &D);143                     printf("%I64d\n",query(L, R, 1, N, T[D], 0));144                     break;145                 case ‘B‘:146                     if (L < t) used = T[L + 1];147                     t = L;148             }149         }150     }151     return 0;152 }