Background
To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we'll give you a chance, to implement the logic behind the scene.
You‘ve been given N integers A [1], A [2],..., A [N]. On these integers, you need to implement the following operations:
1. C l r d: Adding a constant d for every {A i | l <= i <= r}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.
2. Q l r: Querying the current sum of {A i | l <= i <= r}.
3. H l r t: Querying a history sum of {A i | l <= i <= r} in time t.
4. B t: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.
.. N, M ≤ 10 5, |A [i]| ≤ 10 9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10 4 .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won't introduce you to a future state.
To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we'll give you a chance, to implement the logic behind the scene.
You‘ve been given N integers A [1], A [2],..., A [N]. On these integers, you need to implement the following operations:
1. C l r d: Adding a constant d for every {A i | l <= i <= r}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.
2. Q l r: Querying the current sum of {A i | l <= i <= r}.
3. H l r t: Querying a history sum of {A i | l <= i <= r} in time t.
4. B t: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.
.. N, M ≤ 10 5, |A [i]| ≤ 10 9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10 4 .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won't introduce you to a future state.
Input
n m
A 1 A 2 ... A n
... (here following the m operations. )
Output
... (for each query, simply print the result. )
Sample Input
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 2 4 0 0 C 1 1 1 C 2 2 -1 Q 1 2 H 1 2 1
Sample Output
4 55 9 15 0 1
给出 n 个数，m次操作，操作一共分成 4 种
1、[l, r]内的值增加 d， 并且 time + 1
2、查询当前 time 时 [l, r]内的和
3、查询time = t 时 [l, r]内的和
4、把 time 退回到 t
然后对于2、3操作，输出对应的答案。
因为有4操作，所以要用主席树来保留每一个 time 的线段树。
对于区间修改操作，像线段树一样去更新，对于区间的sum，直接更新当前区间内的sum值，但是 update 的时候并不能保证 update 到的区间都被给出的区间所包含，所以需要用(min(r, pr) - max(l, pl) + 1)来确定有几个要更新的点。对于lazy，只有当 update 到的区间完全被给出的区间所包含的时候，才更新 lazy， 这样保证了 sum 不会多加， lazy 不会多标记。
对于区间查询操作，由于在之前更新的时候就已经把当前区间的 sum 求出来了，所以当某个区间完全被查询区间包含，只要直接加上这个区间的 sum 值就可以了。对于lazy，有 lazy 标记的区间，区间内的每个点都要加上 lazy 的值，所以如果我 query 到的区间有 lazy 标记，那么说明我这个区间内的每个点都应该多加 lazy ，给这个区间内需要加 lazy 的值的个数也是 (min(r, pr) - max(l, pl) + 1)
1 /* 2 . 3 ';;;;;. 4 '!;;;;;;!;` 5 '!;|&#@|;;;;!: 6 `;;!&####@|;;;;!: 7 .;;;!&@$$%|!;;;;;;!'.`:::::'. 8 '!;;;;;;;;!$@###&|;;|%!;!$|;;;;|&&;. 9 :!;;;;!$@&%|;;;;;;;;;|!::!!:::;!$%;!$%` '!%&#########@$!:. 10 ;!;;!!;;;;;|$$&@##$;;;::'''''::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$; 11 ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%` 12 `!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&; 13 :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@| 14 ;|::;;;;;;;;;;;;|&&$|;;!$@&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%. 15 `!!;;;;;;;!!!!;;;;;$@@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|. 16 %&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##! 17 !%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&: 18 ':|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%. 19 !@|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&' 20 .:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@: 21 .%$;;;;;;;;;;;;;;;;;;|$$$$@&|;;;;;;;;;;;;;;;;;;;;%@%. 22 !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#; 23 `%$!;;;;;;;;;;;$@|;;;;;;;;;;;;;;;;;;;;;;;;!%$@#@|. 24 .|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%$$$$$@#|. 25 ;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|. 26 |##$|!;;;;;;::'':;;;;;;;;;;;;;!%$$$@#@; 27 ;@&|;;;;;;;::'''''':;;;;;;;|$&@###@|` 28 .%##@|;;;;:::''''''''''::;!%&##$' 29 `$##@$$@@&|!!;;;:'''''::::;;;;;|&#%. 30 ;&@##&$%!;;;;;;::''''''''::;!|%$@#@&@@: 31 .%@&$$|;;;;;;;;;;:'''':''''::;;;%@#@@#%. 32 :@##@###@$$$$$|;;:'''':;;!!;;;;;;!$#@@#$;` 33 `%@$$|;;;;;;;;:'''''''::;;;;|%$$|!!&###&' 34 |##&%!;;;;;::''''''''''''::;;;;;;;!$@&:`!' 35 :;!@$|;;;;;;;::''''''''''':;;;;;;;;!%&@$: !@#$' 36 |##@@&%;;;;;::''''''''':;;;;;;;!%&@#@$%: '%%!%&; 37 |&%!;;;;;;;%$!:''''''':|%!;;;;;;;;|&@%||` '%$|!%&; 38 |@%!;;!!;;;||;:'''''':;%$!;;;;!%%%&#&%$&: .|%;:!&%` 39 !@&%;;;;;;;||;;;:''::;;%$!;;;;;;;|&@%;!$; `%&%!!$&: 40 '$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##; !$!;:!$&: 41 |#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%' `%$|%%;|&$' 42 |&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&; .:%&$!;;;:!$@! 43 `%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@! 44 !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%` 45 '%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%$@@|' 46 .!%%&%'`|$; :|$#%|@#&;%#%. 47 */ 48 #include <map> 49 #include <set> 50 #include <list> 51 #include <ctime> 52 #include <cmath> 53 #include <stack> 54 #include <queue> 55 #include <string> 56 #include <vector> 57 #include <cstdio> 58 #include <bitset> 59 #include <cstdlib> 60 #include <cstring> 61 #include <iostream> 62 #include <algorithm> 63 #define lowbit(x) x & (-x) 64 #define mes(a, b) memset(a, b, sizeof a) 65 #define fi first 66 #define se second 67 #define pii pair<int, int> 68 #define INOPEN freopen("in.txt", "r", stdin) 69 #define OUTOPEN freopen("out.txt", "w", stdout) 70 71 typedef unsigned long long int ull; 72 typedef long long int ll; 73 const int maxn = 1e5 + 10; 74 const int maxm = 1e5 + 10; 75 const ll mod = 1e9 + 7; 76 const ll INF = 1e18 + 100; 77 const int inf = 0x3f3f3f3f; 78 const double pi = acos(-1.0); 79 const double eps = 1e-8; 80 using namespace std; 81 82 int n, m; 83 int cas, tol, T; 84 85 struct Node{ 86 int l, r; 87 ll sum, lazy; 88 } node[maxn * 40]; 89 ll a[maxn]; 90 int rt[maxn]; 91 92 void init() { 93 tol = 0; 94 mes(a, 0); 95 mes(rt, 0); 96 } 97 98 void pushup(int rt) { 99 node[rt].sum = node[node[rt].l].sum + node[node[rt].r].sum; 100 } 101 102 void build(int l, int r, int &rt) { 103 rt = ++tol; 104 node[rt].sum = node[rt].lazy = 0; 105 if(l == r) { 106 node[rt].sum = a[l]; 107 return ; 108 } 109 int mid = (l + r) >> 1; 110 build(l, mid, node[rt].l); 111 build(mid+1, r, node[rt].r); 112 pushup(rt); 113 } 114 115 void update(int l, int r, int &x, int y, int pl, int pr, ll val) { 116 x = ++tol; 117 node[x] = node[y]; 118 node[x].sum += 1ll * (min(r, pr) - max(l, pl) + 1) * val; 119 if(pl <= l && r <= pr) { 120 node[x].lazy += val; 121 return ; 122 } 123 int mid = (l + r) >> 1; 124 if(pl <= mid) 125 update(l, mid, node[x].l, node[y].l, pl, pr, val); 126 if(pr > mid) 127 update(mid+1, r, node[x].r, node[y].r, pl, pr, val); 128 } 129 130 ll query(int l, int r, int pl, int pr, int rt) { 131 if(pl <= l && r <= pr) { 132 return node[rt].sum; 133 } 134 int mid = (l + r) >> 1; 135 ll ans = 1ll * (min(r, pr) - max(l, pl) + 1) * node[rt].lazy; 136 if(pl <= mid) 137 ans += query(l, mid, pl, pr, node[rt].l); 138 if(pr > mid) 139 ans += query(mid+1, r, pl, pr, node[rt].r); 140 return ans; 141 } 142 143 int main() { 144 while(~scanf("%d%d", &n, &m)) { 145 init(); 146 for(int i=1; i<=n; i++) { 147 scanf("%lld", &a[i]); 148 } 149 T = 0; 150 build(1, n, rt[T]); 151 char s[10]; 152 while(m--) { 153 scanf("%s", s+1); 154 if(s[1] == 'C') { 155 int l, r; 156 ll d; 157 scanf("%d%d%lld", &l, &r, &d); 158 T++; 159 update(1, n, rt[T], rt[T-1], l, r, d); 160 } else if(s[1] == 'Q') { 161 int l, r; 162 scanf("%d%d", &l, &r); 163 ll ans = query(1, n, l, r, rt[T]); 164 printf("%lld ", ans); 165 } else if(s[1] == 'H') { 166 int l, r, t; 167 scanf("%d%d%d", &l, &r, &t); 168 ll ans = query(1, n, l, r, rt[t]); 169 printf("%lld ", ans); 170 } else if(s[1] == 'B'){ 171 int t; 172 scanf("%d", &t); 173 T = t; 174 } 175 } 176 } 177 return 0; 178 }