fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 140000;
  6. const int M = 140000;
  7. const int V = 1000000 + 10;
  8.  
  9. struct Qry {
  10. 	int l, r, t, id;
  11. };
  12.  
  13. struct Edt {
  14. 	int p, oldc, newc;
  15. };
  16.  
  17. int a[N];
  18. int cnt[V];
  19. Qry qry[M];
  20. Edt edt[M];
  21. int ans[M];
  22. int res, sz;
  23.  
  24. bool operator < (const Qry& a, const Qry& b) {
  25. 	if (a.l / sz != b.l / sz) return a.l / sz < b.l / sz;
  26. 	if (a.r / sz != b.r / sz) return a.r / sz < b.r / sz;
  27. 	return a.t < b.t;
  28. }
  29.  
  30. void update(int i, int d) {
  31. 	cnt[a[i]] += d;
  32. 	if (d == -1 && cnt[a[i]] == 0) res --;
  33. 	else if (d == 1 && cnt[a[i]] == 1) res ++;
  34. }
  35.  
  36. void change(int i, int c, int l, int r) {
  37. 	if (i >= l && i <= r) {
  38. 		update(i, -1);
  39. 		a[i] = c;
  40. 		update(i, 1);
  41. 	}
  42. 	else a[i] = c;
  43. }
  44.  
  45. int main() {
  46. 	int n, m, tq = 0, te = 0, l, r, t, p, c;
  47. 	char op;
  48. 	scanf("%d %d", &n, &m);
  49. 	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
  50. 	for (int i=0; i<m; i++) {
  51. 		scanf(" %c", &op);
  52. 		if (op == 'Q') {
  53. 			scanf("%d %d", &qry[tq].l, &qry[tq].r);
  54. 			qry[tq].id = tq;
  55. 			qry[tq].t = te;
  56. 			tq ++;
  57. 		}
  58. 		else {
  59. 			scanf("%d %d", &p, &c);
  60. 			edt[te] = {p, a[p], c};
  61. 			a[p] = c;
  62. 			te ++;
  63. 		}
  64. 	}
  65. 	for (int i=te-1; i>=0; i--) a[edt[i].p] = edt[i].oldc;
  66. 	sz = pow(n, 2.0 / 3);
  67. 	///*if (te == 0) sz = sqrt(tq); else*/ sz = ceil(exp((log(n)+log(te))/3));//pow((double)tq * te, 1.0 / 3);
  68. 	sort(qry, qry + tq);
  69. 	l = qry[0].l, r = qry[0].r, t = qry[0].t;
  70. 	for (int i=l; i<=r; i++) update(i, 1);
  71. 	for (int i=0; i<t; i++) change(edt[i].p, edt[i].newc, l, r);
  72. 	ans[qry[0].id] = res;
  73. 	for (int i=1; i<tq; i++) {
  74. 		while (l > qry[i].l) update(-- l, 1);
  75. 		while (r < qry[i].r) update(++ r, 1);
  76. 		while (l < qry[i].l) update(l ++, -1);
  77. 		while (r > qry[i].r) update(r --, -1);
  78. 		while (t < qry[i].t) {
  79. 			change(edt[t].p, edt[t].newc, l, r);
  80. 			t ++;
  81. 		}
  82. 		while (t > qry[i].t) {
  83. 			t --;
  84. 			change(edt[t].p, edt[t].oldc, l, r);
  85. 		}
  86. 		ans[qry[i].id] = res;
  87. 	}
  88. 	for (int i=0; i<tq; i++) printf("%d\n", ans[i]);
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zPOi4m
language:
C++ (gcc 8.3)
created:
11 days 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!