fork(4) download
  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
stdin
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
1
2
0
3
4
2