fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node {
  5. int prior, size, pos;
  6. long long val, sum;
  7. node *l, *r;
  8. };
  9. typedef node* pnode;
  10.  
  11. int sz(pnode t) {
  12. return t ? t->size : 0;
  13. }
  14.  
  15. void upd_sz(pnode t) {
  16. if(t) {
  17. t->size = sz(t->l) + sz(t->r) + 1;
  18. }
  19. }
  20.  
  21. void combine(pnode &t, pnode l, pnode r) {
  22. if(!l || !r) {
  23. t = l ? l : r;
  24. return;
  25. }
  26. t->sum = l->sum + r->sum;
  27. }
  28.  
  29. void reset(pnode t) {
  30. if(t) {
  31. t->sum = t->val;
  32. }
  33. }
  34.  
  35. void operation(pnode t) {
  36. if(!t) {
  37. return;
  38. }
  39. reset(t);
  40. combine(t, t->l, t);
  41. combine(t, t, t->r);
  42. }
  43.  
  44. void split(pnode t, pnode &l, pnode &r, int pos) {
  45. if(!t) {
  46. l = r = NULL;
  47. return;
  48. }
  49.  
  50. if(t->pos <= pos) {
  51. split(t->r, t->r, r, pos);
  52. l = t;
  53. }
  54. else {
  55. split(t->l, l, t->l, pos);
  56. r = t;
  57. }
  58. upd_sz(t);
  59. operation(t);
  60. }
  61.  
  62. void merge(pnode &t, pnode l, pnode r) {
  63. if(!l || !r) {
  64. t = l ? l : r;
  65. }
  66. else if(l->prior > r->prior) {
  67. merge(l->r, l->r, r);
  68. t = l;
  69. }
  70. else {
  71. merge(r->l, l, r->l);
  72. t = r;
  73. }
  74. upd_sz(t);
  75. operation(t);
  76. }
  77.  
  78. void init(pnode &t, int pos = -1, int val = 0) {
  79. t->prior = rand();
  80. t->pos = pos;
  81. t->size = 1;
  82. t->val = val;
  83. t->sum = t->val;
  84. t->l = t->r = NULL;
  85. }
  86.  
  87. const int N = 1e5 + 10;
  88. pnode seg[N << 2];
  89. int A[N];
  90. int Left[N];
  91.  
  92. long long get_sum(pnode t, int pos) {
  93. pnode l, r;
  94. split(t, l, r, pos);
  95. long long ans = l ? l->sum : 0;
  96. merge(t, l, r);
  97. return ans;
  98. }
  99.  
  100. void update(int l, int r, int id, int pos, int old_val, int val, int old_pos, int new_pos) {
  101. pnode L, mid, R;
  102. if(old_pos > -1) {
  103. split(seg[id], L, mid, old_pos-1);
  104. split(mid, seg[id], R, old_pos);
  105.  
  106. if(seg[id]) {
  107. seg[id]->val -= old_val;
  108. seg[id]->sum -= old_val;
  109. }
  110.  
  111. merge(mid, L, seg[id]);
  112. merge(seg[id], mid, R);
  113. }
  114.  
  115.  
  116. split(seg[id], L, mid, new_pos-1);
  117. split(mid, seg[id], R, new_pos);
  118.  
  119. if(seg[id]) {
  120. seg[id]->val += val;
  121. seg[id]->sum += val;
  122. }
  123. else {
  124. seg[id] = new node;
  125. init(seg[id], new_pos, val);
  126. }
  127.  
  128. merge(mid, L, seg[id]);
  129. merge(seg[id], mid, R);
  130.  
  131. if(l == r) {
  132. return;
  133. }
  134.  
  135. int _mid = l + r >> 1;
  136. if(_mid >= pos)
  137. update(l, _mid, id << 1, pos, old_val, val, old_pos, new_pos);
  138. else
  139. update(_mid + 1, r, id << 1 | 1, pos, old_val, val, old_pos, new_pos);
  140. }
  141.  
  142. long long query(int l, int r, int id, int x, int y) {
  143. if(l > y || r < x)
  144. return 0;
  145. if(l >= x && r <= y) {
  146. return get_sum(seg[id], x - 1);
  147. }
  148. int mid = l + r >> 1;
  149. return query(l, mid, id << 1, x, y) + query(mid + 1, r, id << 1 | 1, x, y);
  150. }
  151.  
  152. map < int, set < int > > M;
  153.  
  154. int main() {
  155. int n;
  156. scanf("%d", &n);
  157. for(int i = 1; i <= n; ++i) {
  158. scanf("%d", A + i);
  159.  
  160. M[A[i]].insert(0);
  161.  
  162. auto it = M[A[i]].end();
  163. --it;
  164. Left[i] = *it;
  165.  
  166. M[A[i]].insert(i);
  167. }
  168. for(int i = 1; i <= n; ++i) {
  169. update(1, n, 1, i, 0, A[i], -1, Left[i]);
  170. }
  171.  
  172. int q;
  173. scanf("%d", &q);
  174. for(int i = 1; i <= q; ++i) {
  175. char c;
  176. int x, y;
  177. scanf(" %c %d %d", &c, &x, &y);
  178. if(c == 'Q') {
  179. long long ans = query(1, n, 1, x, y);
  180. printf("%lld\n", ans);
  181. }
  182. else if(A[x] != y) {
  183.  
  184. M[y].insert(0);
  185. auto it = M[y].lower_bound(x);
  186. auto it3 = M[A[x]].upper_bound(x);
  187. auto it2 = it;
  188. --it;
  189. update(1, n, 1, x, A[x], y, Left[x], *it);
  190. if(it2 != M[y].end()) {
  191. update(1, n, 1, *it2, y, y, Left[*it2], x);
  192. Left[*it2] = x;
  193. }
  194. if(it3 != M[A[x]].end()) {
  195. update(1, n, 1, *it3, A[x], A[x], x, Left[x]);
  196. Left[*it3] = Left[x];
  197. }
  198. M[y].insert(x);
  199. M[A[x]].erase(x);
  200. A[x] = y;
  201. Left[x] = *it;
  202.  
  203. }
  204. }
  205.  
  206. }
Success #stdin #stdout 0s 19152KB
stdin
5
1 2 4 2 3                                                                              
3
Q 2 4
U 4 7
Q 2 4
stdout
6
13