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
comments (?)
stdin 
5
1 2 4 2 3                                                                              
3
Q 2 4
U 4 7
Q 2 4
stdout 
6
13
https://ideone.com/sJMdlW
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!