fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define n 200005
  5.  
  6. struct Query{
  7. 	int L,R,Time,noquery; // noquery = Nomor query
  8. }query[n];
  9.  
  10. int N,Q,B,value[n],tmp[n],cnt[n],ans[n],jum,currentL,currentR,currentTime;
  11. pair<int,int> query1[n];
  12.  
  13. bool cmp(Query x,Query y){
  14. 	if(x.L/B != y.L/B) return x.L/B<y.L/B;
  15. 	if(x.R/B != y.R/B) return x.R/B<y.R/B;
  16. 	return x.Time < y.Time;
  17. }
  18. void add(int pos){
  19. 	cnt[value[pos]]++;
  20. 	if(cnt[value[pos]] == 1) jum++;
  21. 	else if(cnt[value[pos]] == 2) jum--;
  22. }
  23.  
  24. void rem(int pos){
  25. 	cnt[value[pos]]--;
  26. 	if(cnt[value[pos]] == 0) jum--;
  27. 	else if(cnt[value[pos]] == 1) jum++;
  28. }
  29.  
  30. void change(int pos){
  31. 	if(query1[pos].first >= currentL && query1[pos].first <= currentR) rem(query1[pos].first);
  32. 	value[query1[pos].first] = query1[pos].second;
  33. 	if(query1[pos].first >= currentL && query1[pos].first <= currentR) 	add(query1[pos].first);
  34. }
  35.  
  36. void reset(){
  37. 	currentTime = 0;
  38. 	for(int i=1;i<=N;i++) {
  39. 		if(value[i] != tmp[i]){ 
  40. 			if(i >= currentL && i <= currentR) rem(i);
  41. 			value[i] = tmp[i];
  42. 			if(i >= currentL && i <= currentR)
  43. 			add(i);
  44. 		}
  45. 	}
  46. }
  47.  
  48. int main(){
  49. 	cin >> N >> Q;
  50. 	B = (double)pow(N,(double)2/3); // size block , bisa N^(2/3) tapi bisa juga menggunakan konstanta sendiri 
  51. 	for(int i=1;i<=N;i++) cin >> value[i],tmp[i] = value[i];
  52. 	int timesekarang = 0,jumlahquery2 = 0;
  53.  
  54. 	for(int i=1;i<=Q;i++){
  55. 		int q;
  56. 		cin >> q;
  57. 		if(q == 1){
  58. 			cin >> query1[timesekarang].first >> query1[timesekarang].second;
  59. 			query1[timesekarang].first++;
  60. 			timesekarang++;
  61. 		}
  62. 		else{
  63. 			int j = jumlahquery2;
  64. 			cin >> query[j].L >> query[j].R;
  65. 			query[j].L++;query[j].R++;
  66. 			query[j].Time = timesekarang;		
  67. 			query[j].noquery = j;
  68. 			jumlahquery2++;
  69. 			// masukin ke struct blok kiri,blok kanan,time ,indeksquery2
  70. 		}
  71. 	}
  72. 	sort(query,query+jumlahquery2,cmp); //sort berdasarkan blok kiri, blok kanan , time
  73. 	jum = 0;//jawaban sementara
  74. 	currentL = 1;currentR = 0;currentTime = 0;
  75. 	for(int i=0;i<jumlahquery2;i++){
  76. 		//mo's
  77. 		int L = query[i].L, R = query[i].R,Time = query[i].Time;
  78. 		while(currentL < L) {
  79. 			rem(currentL);
  80. 		 	currentL++;
  81. 		}
  82. 		while(currentL > L) {
  83. 			add(currentL-1);
  84. 			currentL--;
  85. 		}
  86. 		while(currentR < R) {
  87. 		 	add(currentR+1);
  88. 		 	currentR++;
  89. 		}
  90. 		while(currentR > R) {
  91. 			rem(currentR);
  92. 		 	currentR--;
  93. 		}
  94. 		// kita tambahkan yang buat time
  95. 		if(currentTime > Time){
  96. 			reset(); //karena timenya selalu increasing maka kita dapat lakukan reset karna apabila currentTime > Time maka ia telah berpindah blok
  97. 		}
  98. 		while(currentTime < Time ) {
  99. 			change(currentTime);
  100. 			currentTime++;
  101. 		}
  102. 		ans[query[i].noquery] = jum; // array penyimpanan jawaban
  103. 	}
  104. 	for(int i=0;i<jumlahquery2;i++) cout << ans[i] << "\n";
  105. }
Success #stdin #stdout 0s 23056KB
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/VLgNwh
language:
C++ (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!