fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MX = 2e5 + 5;
  6. int n, q, SZ, Ans = 0, Arr[MX], Answers[MX], last[MX], freq[MX];
  7.  
  8. struct query{
  9. 	// t represents how many updates are there before this query
  10. 	int l, r, t, id;
  11. }Q[MX];
  12.  
  13. struct update{
  14. 	int index, pre, now;
  15. }U[MX];
  16.  
  17. bool cmp(query a, query b){
  18. 	int l1 = a.l/SZ, l2 = b.l/SZ;
  19. 	int r1 = a.r/SZ, r2 = b.r/SZ;
  20.  
  21. 	if(l1 != l2) return l1 < l2;
  22. 	if(r1 != r2) return r1 < r2;
  23. 	return a.t < b.t;
  24. }
  25.  
  26. void add(int x){
  27. 	freq[x]++;
  28. 	if(freq[x] == 1) Ans++;
  29. 	if(freq[x] == 2) Ans--;
  30. }
  31.  
  32. void remove(int x){
  33. 	freq[x]--;
  34. 	if(freq[x] == 0) Ans--;
  35. 	if(freq[x] == 1) Ans++;
  36. }
  37.  
  38. void apply(int x, int val, int l, int r){
  39. 	if(x >= l && x <= r){
  40. 		remove(Arr[x]);
  41. 		Arr[x] = val;
  42. 		add(Arr[x]);
  43. 	}else{
  44. 		Arr[x] = val;
  45. 	}
  46. }
  47.  
  48. int main(){
  49. 	int id, q_id = 0, u_id = 0, l, r, val;
  50. 	scanf("%d %d", &n, &q);
  51. 	SZ = sqrt(n);
  52. 	for(int i = 0; i < n; scanf("%d", &Arr[i]), last[i] = Arr[i], i++);
  53.  
  54. 	for(int i = 0; i < q; i++){
  55. 		scanf("%d", &id);
  56. 		if(id == 1){
  57. 			scanf("%d %d", &l, &val);
  58. 			U[u_id++] = {l, last[l], val};
  59. 			last[l] = val;
  60. 		}else{
  61. 			scanf("%d %d", &l, &r);
  62. 			Q[q_id].l = l;
  63. 			Q[q_id].r = r;
  64. 			Q[q_id].t = u_id;
  65. 			Q[q_id].id = q_id;
  66. 			q_id++;
  67. 		}
  68. 	}
  69.  
  70. 	sort(Q, Q + q_id, cmp);
  71. 	int mo_left = 0, mo_right = -1, t = 0;
  72.  
  73. 	for(int i = 0; i < q_id; i++){
  74. 		l = Q[i].l, r = Q[i].r; 
  75.  
  76. 		for(; mo_right < r ; mo_right++, add(Arr[mo_right]));
  77. 		for(; mo_right > r ; remove(Arr[mo_right]), mo_right--);
  78. 		for(; mo_left < l ; remove(Arr[mo_left]), mo_left++);
  79. 		for(; mo_left > l ; mo_left--, add(Arr[mo_left]));
  80.  
  81. 		for(; t < Q[i].t ; apply(U[t].index, U[t].now, l, r), t++);
  82. 		for(; t > Q[i].t ; t--, apply(U[t].index, U[t].pre, l, r));
  83.  
  84. 		Answers[Q[i].id] = Ans;
  85. 	}
  86.  
  87. 	for(int i = 0; i < q_id; i++){
  88. 		printf("%d\n", Answers[i]);
  89. 	}
  90.  
  91.  
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 24656KB
comments (?)
stdin
copy 
8 8
1 2 3 3 1 2 3 3
2 1 3
2 0 3 
2 0 7
1 3 4
1 7 0
2 1 3
2 0 3 
2 0 7
stdout
copy 
1
2
0
3
4
2
https://ideone.com/srH91b
language:
C++14 (gcc 8.3)
created:
6 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!