主席树

原理

1、对于修改的值，在线段树中只会从该点到根的一条链中的信息被修改，我们对这些被修改的结点新建点，其他不变的点连回原来的线段树结点。这样就实现了历史版本的保存和新版本的建立。

2、对于[1,n]的数组（离散化排序），对每个前缀维护一颗线段树。

3、对树上的区间查询，以到根的距离作为“前缀”维护主席树。也就是说，对整棵树初始化主席树时，当前结点其历史版本为其父亲。

4、对含修改的查询，采用树状数组来维护变化量，树状数组的每个结点代表一棵线段树，整个树状数组可看成一个变化的主席树。

题目

1、K-th Number POJ - 2104

　　题意：m次询问某个区间第k小(区间从小到大第k个)的数。

　　思路：主席树模板题。线段树结点维护区间内含有多少个数。对所有结点的权值离散化，每个下标到首位置建立前缀和。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 1e5 + 6;
 6 int n, m;//n个数，m次询问
 7 /*主席树*/
 8 int cnt;//主席树结点编号
 9 int root[maxn];//线段树的根的编号
10 struct NODE
11 {
12     int lson, rson;
13     int sum;//区间内数的个数
14     NODE(int ll=0,int rr=0,int ss=0):lson(ll),rson(rr),sum(ss){}
15 }tree[maxn*20];
16 void init()
17 {
18     cnt = 0;
19     root[0] = 0;
20     tree[0].lson = tree[0].rson = tree[0].sum = 0;
21 }
22 void update(int &rt,int pre, int l, int r, int pos)
23 {
24     tree[++cnt] = tree[pre],tree[cnt].sum++,rt=cnt;//修改的新加入
25     if (l == r) return;
26     int mid = (l + r) / 2;
27     if (pos <= mid) update(tree[rt].lson,tree[pre].lson,l, mid, pos);
28     else update(tree[rt].rson,tree[pre].rson,mid + 1, r, pos);
29 }
30 int Query(int rl, int rr, int l, int r, int k)
31 {
32     if (l == r) return l;
33     int rem = tree[tree[rr].lson].sum - tree[tree[rl].lson].sum;
34     int mid = (l + r) / 2;
35     if (k <= rem) return Query(tree[rl].lson, tree[rr].lson, l, mid, k);
36     else return Query(tree[rl].rson, tree[rr].rson, mid + 1, r, k-rem);
37 }
38 
39 struct VAL
40 {
41     int v;
42     int id;
43     friend bool operator<(const VAL&v1, const VAL&v2)
44     {
45         return v1.v < v2.v;
46     }
47 }V[maxn];//用于离散化
48 int nid[maxn];//原数组第i个数离散化后的编号
49 int main()
50 {
51     while (~scanf("%d%d", &n, &m))
52     {
53         for (int i = 1; i <= n; i++) scanf("%d", &V[i].v),V[i].id=i;
54         sort(V + 1, V + 1 + n);
55         for (int i = 1; i <= n; i++) nid[V[i].id] = i;
56         init();
57         for (int i = 1; i <= n; i++)
58         {
59             update(root[i],root[i-1],1, n, nid[i]);
60         }
61         for (int i = 1; i <= m; i++)
62         {
63             int l, r, k;
64             scanf("%d%d%d", &l, &r, &k);
65             printf("%d
", V[Query(root[l - 1], root[r], 1, n, k)].v);
66         }
67     }
68     return 0;
69 }

View Code

2、Count on a tree SPOJ - COT

　　题意：在一棵树上，询问点对之间点权值第k小的值为多少。

　　思路：主席树+LCA。同样，先对所有结点的权值离散化，然后建线段树，每个点以其父亲为历史版本(以每个点到根结点建立前缀和)。对于点对[l,r]，其内含有的数的个数为sum[l]+sum[r]-sum[lca(l,r)]-sum[pre[lca(u,v)]]。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<vector>
  6 using namespace std;
  7 const int maxn = 100000 + 7;
  8 
  9 struct EDGE
 10 {
 11     int to, next;
 12     EDGE(int tt=0,int nn=0):to(tt),next(nn){}
 13 }edge[maxn<<1];
 14 int Head[maxn], totedge;
 15 void addedge(int from, int to)
 16 {
 17     edge[totedge] = EDGE(to, Head[from]);
 18     Head[from] = totedge++;
 19     edge[totedge] = EDGE(from, Head[to]);
 20     Head[to] = totedge++;
 21 }
 22 void init()
 23 {
 24     memset(Head, -1, sizeof(Head));
 25     totedge = 0;
 26 }
 27 int n, m;
 28 /*LCA*/
 29 int dp[maxn<<1][30];  //这个数组记得开到2*N，因为遍历后序列长度为2*n-1
 30 bool vis[maxn];
 31 int ver[maxn << 1],tot;//dfs序
 32 int R[maxn << 1];//dfs序对应点的深度
 33 int first[maxn], dir[maxn];//每个结点在dfs序中第一次出现的位置、距离
 34 void dfs(int u,int fa, int dep)
 35 {
 36     vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep;
 37     for (int k = Head[u]; k != -1; k = edge[k].next)
 38         if (!vis[edge[k].to])
 39         {
 40             int v = edge[k].to, w =1;
 41             dir[v] = dir[u] + w;
 42             dfs(v,u, dep + 1);
 43             ver[++tot] = u; R[tot] = dep;
 44         }
 45 }
 46 void ST(int n)
 47 {
 48     for (int i = 1; i <= n; i++)
 49         dp[i][0] = i;
 50     for (int j = 1; (1 << j) <= n; j++)
 51     {
 52         for (int i = 1; i + (1 << j) - 1 <= n; i++)
 53         {
 54             int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];
 55             dp[i][j] = R[a]<R[b] ? a : b;
 56         }
 57     }
 58 }
 59 //中间部分是交叉的。
 60 int RMQ(int l, int r)
 61 {
 62     int k = 0;
 63     while ((1 << (k + 1)) <= r - l + 1)
 64         k++;
 65     int a = dp[l][k], b = dp[r - (1 << k) + 1][k]; //保存的是编号
 66     return R[a]<R[b] ? a : b;
 67 }
 68 
 69 int LCA(int u, int v)
 70 {
 71     int x = first[u], y = first[v];
 72     if (x > y) swap(x, y);
 73     int res = RMQ(x, y);
 74     return ver[res];
 75 }
 76 /*LCA·终*/
 77 int root[maxn];
 78 struct node
 79 {
 80     int lson, rson;
 81     int sum;
 82 }tree[maxn*20];
 83 int node_cnt;
 84 void BuildTree(int &rt, int l, int r)
 85 {
 86     rt = ++node_cnt;
 87     tree[rt].sum = 0;
 88     if (l == r) return;
 89     int mid = (l + r) / 2;
 90     BuildTree(tree[rt].lson, l, mid);
 91     BuildTree(tree[rt].rson, mid + 1, r);
 92 }
 93 void update(int &rt, int l, int r, int pre_rt, int pos)
 94 {
 95     tree[++node_cnt] = tree[pre_rt], rt = node_cnt, tree[rt].sum++;
 96     if (l == r) return;
 97     int mid = (l + r) / 2;
 98     if (pos <= mid) update(tree[rt].lson, l, mid, tree[pre_rt].lson, pos);
 99     else update(tree[rt].rson, mid + 1, r, tree[pre_rt].rson, pos);
100 }
101 int query(int rl, int rr,int lca_r,int fa_lca_r, int l, int r, int k)
102 {
103     if (l == r)return l;
104     int mid = (l + r) / 2;
105     int rem = tree[tree[rr].lson].sum + tree[tree[rl].lson].sum- tree[tree[lca_r].lson].sum - tree[tree[fa_lca_r].lson].sum;
106     if (k <= rem) return query(tree[rl].lson, tree[rr].lson, tree[lca_r].lson,tree[fa_lca_r].lson, l, mid, k);
107     else return query(tree[rl].rson, tree[rr].rson, tree[lca_r].rson,tree[fa_lca_r].rson, mid+1,r, k-rem);
108 }
109 int val[maxn], nid[maxn];
110 vector<int>f_val;//离散化
111 int pre[maxn],sz;
112 void updatetree(int u, int fa)
113 {
114     pre[u] = fa;
115     update(root[u], 1, sz, root[fa], nid[u]);
116     for (int i = Head[u]; i != -1; i = edge[i].next)
117     {
118         int v = edge[i].to;
119         if (v != fa) updatetree(v, u);
120     }
121 }
122 
123 int main()
124 {
125     while (~scanf("%d%d", &n, &m))
126     {
127         init();
128         f_val.clear();
129         node_cnt = 0;
130         for (int i = 1; i <= n; i++) scanf("%d", &val[i]), f_val.push_back(val[i]);
131         sort(f_val.begin(), f_val.end());
132         f_val.erase(unique(f_val.begin(), f_val.end()), f_val.end());
133         sz = f_val.size();
134         for (int i = 1; i <= n; i++)
135         {
136             nid[i] = lower_bound(f_val.begin(), f_val.end(), val[i]) - f_val.begin()+1;
137         }
138         for (int i = 1; i <= n - 1; i++)
139         {
140             int u, v;
141             scanf("%d%d", &u, &v);
142             addedge(u, v);
143         }
144         BuildTree(root[0], 1,sz);
145         updatetree(1, 0);
146 
147         dfs(1,0, 1);
148         ST(2 * n - 1);
149         
150         for (int i = 1; i <= m; i++)
151         {
152             int u, v, k;
153             scanf("%d%d%d", &u, &v, &k);
154             int id_lca = LCA(u, v);
155             int ans = query(root[u], root[v], root[id_lca], root[pre[id_lca]], 1, sz, k);
156             printf("%d
", f_val[ans - 1]);
157         }
158     }
159 
160 
161     return 0;
162 }

View Code

3、Dynamic Rankings ZOJ - 2112

　　题意：在一个含有n个数的数组中，每次询问区间第k小或者修改某个数的值。

　　思路：动态主席树。先对所有询问离散化，对初始数组建立主席树root[maxn]。之后用树状数组tree[maxn]来维护修改信息，用空树对树状数组初始化（树状数组每个结点代表一个线段树，采用主席树的思想更新值）。每次修改一个值，相当于原值个数-1，新值个数+1，这个用树状数组上建立的主席树来维护。每次统计区间[l,r]内的个数为(sum[r]-sum[l-1])+(query(r)-query(l-1))，前一部分为原始数组的个数，后一部分是修改的个数。为了方便query，用cur[maxn]来表示当前使用的树状数组结点来统计和。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<vector>
  4 #include<cstdio>
  5 using namespace std;
  6 const int maxn = 60000 + 7;
  7 const int maxm = 10000 + 7;
  8 int val[maxn];//记录原始数组
  9 vector<int>all;//记录所有原始值和修改值，用作离散
 10 int n, m;
 11 int sz;
 12 struct node
 13 {
 14     int l, r, k, type;
 15 }qs[maxm];//离线所有查询操作
 16 
 17 int root[maxn],lson[maxn*40], rson[maxn*40], sum[maxn*40],cnt;//主席树(只需对初始数组建立主席树)
 18 int BuildTree(int l, int r)
 19 {
 20     int rt = ++cnt;
 21     sum[rt] = 0;
 22     if (l == r) return rt;
 23     int mid = (l + r) / 2;
 24     lson[rt] = BuildTree(l, mid);
 25     rson[rt] = BuildTree(mid + 1, r);
 26     return rt;
 27 }
 28 int insert( int pre_rt, int l, int r, int pos,int v)
 29 {
 30     int rt = ++cnt;
 31     lson[rt] = lson[pre_rt], rson[rt] = rson[pre_rt], sum[rt] = sum[pre_rt] + v;
 32     if (l == r) return rt;
 33     int mid = (l + r) / 2;
 34     if (pos <= mid) lson[rt]=insert( lson[pre_rt], l, mid, pos,v);
 35     else rson[rt]=insert( rson[pre_rt], mid + 1, r, pos,v);
 36     return rt;
 37 }
 38 int get_id(int v)
 39 {
 40     return lower_bound(all.begin(), all.end(), v) - all.begin()+1;
 41 }
 42 int tree[maxn],cur[maxn];//树状数组
 43 int lowbit(int x)
 44 {
 45     return x & (-x);
 46 }
 47 void update(int x, int pos, int v)
 48 {
 49     while (x <= n)
 50     {
 51         tree[x] = insert(tree[x], 1, sz, pos, v);
 52         x += lowbit(x);
 53     }
 54 }
 55 int query(int x)
 56 {
 57     int ret = 0;
 58     while (x > 0)
 59     {
 60         ret += sum[lson[cur[x]]];
 61         x -= lowbit(x);
 62     }
 63     return ret;
 64 }
 65 int ask(int l,int r, int k)
 66 {
 67     int rl = root[l-1], rr = root[r];
 68     for (int i = l-1; i > 0; i -= lowbit(i)) cur[i] = tree[i];
 69     for (int i = r; i > 0; i -= lowbit(i)) cur[i] = tree[i];
 70     int L = 1, R = sz;
 71     while (L < R)
 72     {
 73         int mid = (L + R) / 2;
 74         int tmp = query(r) - query(l-1) + sum[lson[rr]] - sum[lson[rl]];
 75         if (tmp >= k)
 76         {
 77             R = mid;
 78             for (int i = l-1; i > 0; i -= lowbit(i)) cur[i] = lson[cur[i]];
 79             for (int i = r; i > 0; i -= lowbit(i)) cur[i] = lson[cur[i]];
 80             rl = lson[rl], rr = lson[rr];
 81         }
 82         else
 83         {
 84             L = mid + 1;
 85             k -= tmp;
 86             for (int i = l-1; i > 0; i -= lowbit(i)) cur[i] = rson[cur[i]];
 87             for (int i = r; i > 0; i -= lowbit(i)) cur[i] = rson[cur[i]];
 88             rl = rson[rl], rr = rson[rr];
 89         }
 90     }
 91     return L;
 92 }
 93 void modify(int pos, int v)
 94 {
 95     update(pos, get_id(val[pos]), -1);
 96     update(pos, get_id(v), 1);
 97     val[pos] = v;
 98 }
 99 int main()
100 {
101     int t;
102     scanf("%d", &t);
103     while (t--)
104     {
105         scanf("%d%d", &n, &m);
106         all.clear();
107         for (int i = 1; i <= n; i++) scanf("%d", &val[i]), all.push_back(val[i]);
108         char s[10];
109         for (int i = 1; i <= m; i++)
110         {
111             scanf("%s", s);
112             if (s[0] == 'Q')
113             {
114                 scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
115                 qs[i].type = 1;
116             }
117             else
118             {
119                 scanf("%d%d", &qs[i].l, &qs[i].k);
120                 all.push_back(qs[i].k);
121                 qs[i].type = 2;
122             }
123         }
124         sort(all.begin(),all.end());
125         all.erase(unique(all.begin(), all.end()), all.end());
126         sz = all.size();
127         cnt = 0;
128         root[0] = BuildTree(1, sz);
129         for (int i = 1; i <= n; i++) root[i]=insert( root[i - 1], 1, sz, get_id(val[i]),1);
130         
131         for (int i = 1; i <= n; i++) tree[i] = root[0];
132         for (int i = 1; i <= m; i++)
133         {
134             if (qs[i].type == 1) printf("%d
", all[ask(qs[i].l, qs[i].r, qs[i].k) - 1]);
135             else modify(qs[i].l, qs[i].k);
136         }
137 
138 
139     }
140 
141 
142     return 0;
143 }

View Code

4、Super Mario HDU - 4417

　　题意：有一个数组，求区间内值小于等于h的个数。

　　思路：

　　①对区间[l,r]，二分找到刚好小于等于h的数为第k大，因为主席树记录的是区间内数的个数，如果该个数小于等于k，那么ans+=k。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 1e5 + 6;
 6 int n, m;//n个数，m次询问
 7          /*主席树*/
 8 int cnt;//主席树结点编号
 9 int root[maxn];//线段树的根的编号
10 int ans;//区间内小于等于第k小的个数
11 struct NODE
12 {
13     int lson, rson;
14     int sum;//区间内数的个数
15     NODE(int ll = 0, int rr = 0, int ss = 0) :lson(ll), rson(rr), sum(ss) {}
16 }tree[maxn * 20];
17 void init()
18 {
19     cnt = 0;
20     root[0] = 0;
21     tree[0].lson = tree[0].rson = tree[0].sum = 0;
22 }
23 void update(int &rt, int pre, int l, int r, int pos)
24 {
25     tree[++cnt] = tree[pre], tree[cnt].sum++, rt = cnt;//修改的新加入
26     if (l == r) return;
27     int mid = (l + r) / 2;
28     if (pos <= mid) update(tree[rt].lson, tree[pre].lson, l, mid, pos);
29     else update(tree[rt].rson, tree[pre].rson, mid + 1, r, pos);
30 }
31 int Query(int rl, int rr, int l, int r, int k)
32 {
33     if (l == r)
34     {
35         ans += tree[rr].sum - tree[rl].sum;
36         return l;
37     }
38     int rem = tree[tree[rr].lson].sum - tree[tree[rl].lson].sum;
39     int mid = (l + r) / 2;
40     if (k <= rem) return Query(tree[rl].lson, tree[rr].lson, l, mid, k);
41     else
42     {
43         int id= Query(tree[rl].rson, tree[rr].rson, mid + 1, r, k - rem);
44         ans += rem;
45         return id;
46     }
47 }
48 
49 struct VAL
50 {
51     int v;
52     int id;
53     friend bool operator<(const VAL&v1, const VAL&v2)
54     {
55         return v1.v < v2.v;
56     }
57 }V[maxn];//用于离散化
58 int nid[maxn];//原数组第i个数离散化后的编号
59 int main()
60 {
61     int t;
62     scanf("%d", &t);
63     int Case = 1;
64     while (t--)
65     {
66         printf("Case %d:
", Case++);
67         scanf("%d%d", &n, &m);
68         for (int i = 1; i <= n; i++) scanf("%d", &V[i].v), V[i].id = i;
69         sort(V + 1, V + 1 + n);
70         for (int i = 1; i <= n; i++) nid[V[i].id] = i;
71         init();
72         for (int i = 1; i <= n; i++)
73         {
74             update(root[i], root[i - 1], 1, n, nid[i]);
75         }
76         for (int i = 1; i <= m; i++)
77         {
78             int l, r, h;
79             scanf("%d%d%d", &l, &r, &h);
80             l++, r++;
81             int L = 1, R = r - 1 + 1;
82             int k = L;
83             while (L <= R)
84             {
85                 int mid = (L + R) / 2;
86                 int tmp = V[Query(root[l - 1], root[r], 1, n, mid)].v;
87                 if (tmp <= h)k=mid, L=mid+1;
88                 else R=mid-1;
89             }
90             ans = 0;
91             int id=Query(root[l - 1], root[r], 1, n,k);
92             if (V[id].v > h) printf("0
");
93             else printf("%d
", ans);
94         }
95     }
96     return 0;
97 }

View Code

　　②离线操作，将所有的h和原始的数组的数放在一起离散化。这样，当询问区间内小于等于h的个数时，相当于询问[1,id[h]]区间内数的个数。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 const int maxn = 1e5 + 6;
 7 int n, m;//n个数，m次询问
 8          /*主席树*/
 9 int cnt;//主席树结点编号
10 int root[maxn];//线段树的根的编号
11 int sz;
12 int ans;
13 struct NODE
14 {
15     int lson, rson;
16     int sum;//区间内数的个数
17     NODE(int ll = 0, int rr = 0, int ss = 0) :lson(ll), rson(rr), sum(ss) {}
18 }tree[maxn * 20];
19 
20 void Build(int &rt,int l,int r)
21 {
22     rt = ++cnt;
23     tree[rt].sum = tree[rt].lson=tree[rt].rson=0;
24     if (l == r) return;
25     int mid = (l + r) / 2;
26     Build(tree[rt].lson, l, mid);
27     Build(tree[rt].rson, mid + 1, r);
28 }
29 void update(int &rt, int pre, int l, int r, int pos)
30 {
31     tree[++cnt] = tree[pre], tree[cnt].sum++, rt = cnt;//修改的新加入
32     if (l == r) return;
33     int mid = (l + r) / 2;
34     if (pos <= mid) update(tree[rt].lson, tree[pre].lson, l, mid, pos);
35     else update(tree[rt].rson, tree[pre].rson, mid + 1, r, pos);
36 }
37 int Query(int rl, int rr, int l, int r, int L,int R)
38 {//查询区间[L,R]内数的个数
39     if (L <= l && r <= R) return tree[rr].sum - tree[rl].sum;
40     int mid = (l + r) / 2;
41     int tans = 0;
42     if (L<=mid) tans+=Query(tree[rl].lson, tree[rr].lson, l, mid, L,R);
43     if (R > mid) tans += Query(tree[rl].rson, tree[rr].rson, mid + 1, r, L, R);
44     return tans;
45 }
46 
47 int val[maxn];
48 vector<int>all;//用于离散化
49 struct OP
50 {
51     int l, r, h;
52 }ops[maxn];
53 int get_id(int v)
54 {
55     return lower_bound(all.begin(), all.end(), v) - all.begin() + 1;
56 }
57 int main()
58 {
59     int t;
60     scanf("%d", &t);
61     int Case = 1;
62     while (t--)
63     {
64         printf("Case %d:
", Case++);
65         scanf("%d%d", &n, &m);
66         all.clear();
67         for (int i = 1; i <= n; i++) scanf("%d", &val[i]),all.push_back(val[i]);
68         for (int i = 1; i <= m; i++)
69         {
70             scanf("%d%d%d", &ops[i].l, &ops[i].r, &ops[i].h);
71             ops[i].l++, ops[i].r++;
72             all.push_back(ops[i].h);
73         }
74         sort(all.begin(), all.end());
75         all.erase(unique(all.begin(), all.end()), all.end());
76         sz = all.size();
77         cnt = 0;
78         Build(root[0], 1, sz);
79         for (int i = 1; i <= n; i++) update(root[i], root[i - 1], 1, sz, get_id(val[i]));
80         for (int i = 1; i <= m; i++)
81         {
82             int id = get_id(ops[i].h);
83             int ans = Query(root[ops[i].l - 1], root[ops[i].r], 1, sz, 1, id);
84             printf("%d
", ans);
85         }
86     }
87     return 0;
88 }

View Code

5、To the moon HDU - 4348

　　题意：有一个数组，当前时间为0，执行若干种操作：区间内的数都加上一个值，时间+1；查询当前区间和；查询过去某个时间的区间和；回到过去某个时间，当前时间变为该过去时间。

　　思路：主席树。采用lazy标记记录更新值，但并不将其pushdown，统计结果的时候，从上到下传递累计的lazy，到达可以统计的结点则为自身和加上累计改变值*区间长度。将时间作为前缀建立主席树。注意sum、lazy数组采用long long输入输出。记录一个错误：如果对一个long long的a，scanf("%d",&a)，然后输出a会出错。必须scanf("%I64d",&a)。

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 1e5 + 10;
 4 int n, m;
 5 int root[maxn], lson[maxn * 40], rson[maxn *40];
 6 long long sum[maxn *40], lazy[maxn * 40];
 7 int cnt;
 8 void PushUp(int rt, int l, int r)
 9 {
10     sum[rt] = sum[lson[rt]] + sum[rson[rt]] +lazy[rt]*(r-l+1);
11 }
12 void BuildTree(int &rt, int l, int r)
13 {
14     rt = ++cnt;
15     lazy[rt] = 0;
16     if (l == r)
17     {
18         scanf("%I64d", &sum[rt]);
19         return;
20     }
21     int mid = (l + r) / 2;
22     BuildTree(lson[rt], l, mid);
23     BuildTree(rson[rt], mid + 1, r);
24     PushUp(rt, l, r);
25 }
26 void update(int &rt, int pre_rt, int L, int R, int l, int r, int v)
27 {
28     rt = ++cnt, lson[rt] = lson[pre_rt], rson[rt] = rson[pre_rt], sum[rt] = sum[pre_rt], lazy[rt] = lazy[pre_rt];
29     if (l <= L && R <= r)
30     {
31         lazy[rt] += v;
32         sum[rt] += 1ll * v*(R - L + 1);
33         return;
34     }
35     int mid = (L + R) / 2;
36     if (l <= mid) update(lson[rt], lson[pre_rt], L, mid, l, r, v);
37     if (r > mid) update(rson[rt], rson[pre_rt], mid + 1,R,l, r, v);
38     PushUp(rt, L, R);
39 }
40 long long query(int rt, int L, int R, int l, int r, long long add)
41 {
42     if (l <= L && R <= r)
43     {
44         return sum[rt] + add*(R - L + 1);
45     }
46     int mid = (L + R) / 2;
47     long long ans = 0;
48     if (l <= mid) ans += query(lson[rt], L, mid, l, r, add + lazy[rt]);
49     if (r > mid) ans += query(rson[rt], mid + 1, R, l, r, add + lazy[rt]);
50     PushUp(rt, L, R);
51     return ans;
52 }
53 int main()
54 {
55     while (~scanf("%d%d", &n, &m))
56     {
57         cnt = 0;
58         int cur = 0;
59         BuildTree(root[0], 1, n);
60         char s[10];
61         for (int i = 1; i <= m; i++)
62         {
63             scanf("%s", s);
64             if (s[0] == 'Q')
65             {
66                 int l, r;
67                 scanf("%d%d", &l, &r);
68                 printf("%I64d
", query(root[cur], 1, n, l, r, 0));
69             }
70             else if (s[0] == 'C')
71             {
72                 int l, r, v;
73                 scanf("%d%d%d", &l, &r, &v);
74                 update(root[cur + 1], root[cur], 1, n, l, r, v);
75                 cur++;
76             }
77             else if (s[0] == 'H')
78             {
79                 int l, r, old_t;
80                 scanf("%d%d%d", &l, &r, &old_t);
81                 printf("%I64d
", query(root[old_t], 1, n, l, r, 0));
82             }
83             else
84             {
85                 int old_t;
86                 scanf("%d", &old_t);
87                 cur = old_t;
88                 cnt = root[cur + 1];
89             }
90         }
91     }
92     return 0;
93 }

View Code