fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1e5 + 10;
  6. const int B = sqrt(MAXN);		// 1/2 of maximum answer for any query
  7. const int L = 600;				// Size of block size of sqrt decomposition
  8.  
  9. // Question input parameters.
  10. int n, m, a[MAXN];
  11. // Frequency of frequency computation: [block x][block y][frequency_count]
  12. // This is required to be stored will 2 * sqrt(N) only.
  13. int cnt[MAXN / L + 1][MAXN / L + 1][2 * B + 1];
  14. // For left to right processing: [block x][block y][index]
  15. int dp1[MAXN / L + 1][MAXN / L + 1][2 * B + 1];
  16. // For right to left processing: [block x][block y][index]
  17. int dp2[MAXN / L + 1][MAXN / L + 1][2 * B + 1];
  18. // store frequency of array A.
  19. int cntA[MAXN];
  20. // store frequency of frequency.
  21. int cntCnt[MAXN];
  22.  
  23. map<int, int> compress;
  24.  
  25. int32_t main() {
  26. 	scanf("%d%d", &n, &m);
  27. 	/*
  28. 	Scan the input asn compress the numbers so that they are int he range [1 .. n]
  29. 	and we don't need to use map to store the frequency. A normal array can be
  30. 	used for future purposes. This eliminates additional log(N) factor as well.
  31. 	Note that it can be done here as the frequency of elements matter not the 
  32. 	element itself.
  33. 	*/
  34. 	for(int i = 1; i <= n; i++) {
  35. 		scanf("%d", &a[i]);
  36. 		compress[a[i]];
  37. 	}
  38. 	int tt = 1;
  39. 	for(auto &item : compress) {
  40. 	    item.second = tt++;
  41. 	}
  42. 	for(int i = 1; i <= n; i++) {
  43. 	    a[i] = compress[a[i]];
  44. 	}
  45.  
  46. 	/*
  47. 	Pre-processing for blocks. Note that blocks are 0-indexed while the array is
  48. 	1-indexed in author solution. This is because the block number for a index
  49. 	"x" is calculated as "x/L", which essentially starts from 0.
  50. 	"r" denotes the maximum number of blocks.
  51. 	*/
  52. 	int r = n / L + 1;
  53. 	for(int i = 0; i < r; i++) {
  54. 		// Reset the frequency arrays.
  55. 		for(int j = 0; j < MAXN; j++) {
  56. 			cntA[j] = 0;
  57. 			cntCnt[j] = 0;
  58. 		}
  59. 		for(int j = i; j < r; j++) {
  60. 			/*
  61. 			Precompute the answer for given block first.
  62. 			The general idea is to remove previous contribution in frequency of
  63. 			 frequency table and then update with the new values found.
  64. 			*/
  65. 			for(int k = j * L; k < (j + 1) * L; k++) {
  66. 				if(k < 1 || k > n) continue;
  67. 				if(cntA[a[k]] != 0) {
  68. 					cntCnt[cntA[a[k]]]--;
  69. 				}
  70. 				cntA[a[k]]++;
  71. 				cntCnt[cntA[a[k]]]++;
  72.  
  73. 			}
  74. 			/*
  75. 			Store the important frequency of frequencies i.e. below 2*sqrt(N)
  76. 			across 2 blocks, first starting at block[i] and second ending at
  77. 			block[j].
  78. 			*/
  79. 			for(int k = 1; k < 2 * B + 1; k++) {
  80. 				cnt[i][j][k] = cntCnt[k];
  81. 			}
  82. 			/*
  83. 			Store the frequency of number from starting position of block[i] to
  84. 			some position in block[j] or block[j-1] in left to right and right
  85. 			to left fashion in 2 different tables.
  86. 			*/
  87. 			for(int k = 1; k <= L; k++) {
  88. 				if(i * L - k > 0) {
  89. 					dp1[i][j][k] = cntA[a[i * L - k]];
  90. 				}
  91. 				if((j + 1) * L - 1 + k <= n) {
  92. 					dp2[i][j][k] = cntA[a[(j + 1) * L - 1 + k]];
  93. 				}
  94. 			}
  95. 		}
  96. 	}
  97. 	/*
  98. 	Clear the frequency tables.
  99. 	*/
  100. 	for(int i = 0; i < MAXN; i++) {
  101. 		cntCnt[i] = 0;
  102. 		cntA[i] = 0;
  103. 	}
  104.  
  105. 	int prev_ans = 0;
  106. 	for(int i = 0; i < m; i++) {
  107. 		int l, r;
  108. 		scanf("%d%d", &l, &r);
  109. 		l ^= prev_ans; r ^= prev_ans;
  110. 		int blockL = l / L, blockR = r / L;
  111. 		if(blockL == blockR || blockL + 1 == blockR) {
  112. 			/*
  113. 			Both index belong to same block or adjacent blocks. We can't use
  114. 			the block to block information here as no complete blocks are found.
  115. 			Since size of each block is upto sqrt(N) (The author choses bit more
  116. 			i.e. 600), a brute force solution can be applied here.
  117. 			*/
  118. 			for(int k = l; k <= r; k++) {
  119. 				if(cntA[a[k]] != 0) {
  120. 					cntCnt[cntA[a[k]]]--;
  121. 				}
  122. 				cntA[a[k]]++;
  123. 				cntCnt[cntA[a[k]]]++;
  124. 			}
  125. 			/*
  126. 			Find the mex of the frequency. Though the loop looks like an infinite
  127. 			one, it will terminate in atmost 2*sqrt(N) steps as explained in the
  128. 			editorial.
  129. 			*/
  130. 			for(int i = 1; ; i++) {
  131. 				if(cntCnt[i] == 0) {
  132. 					prev_ans = i;
  133. 					break;	
  134. 				}
  135. 			}
  136. 			/*
  137. 			Bring back the frequency table to initial state i.e. all zeros.
  138. 			Instead of clearing the full table using memset or fill, the
  139. 			complexity will become O(N) per query. We know here most of the
  140. 			elements will be zeros. Only the once updated in this query need to
  141. 			be cleared. Thus just reverse the first operation (Just paste code
  142. 			in reverse order :P)
  143. 			*/
  144. 			for(int k = l; k <= r; k++) {
  145. 				cntCnt[cntA[a[k]]]--;
  146. 				cntA[a[k]]--;
  147. 				if(cntA[a[k]] != 0) cntCnt[cntA[a[k]]]++;
  148. 			}
  149. 		}
  150. 		else {
  151. 			int x = blockL + 1, y = blockR - 1;
  152. 			/*
  153. 			The complete blocks are from "x" to "y". For them we had already
  154. 			caclulated the frequency of desired elements (i.e. upto 2*sqrt(N))
  155. 			in cnt table. We will use this information below and thus avoid
  156. 			traversing through these blocks.
  157. 			Now in the next 2 loops we add the contribution of remaining elements
  158. 			i.e. those lying in not fully covered blocks (x-1 and y+1). We
  159. 			traverse each element one by one and we had already stored the
  160. 			frequency of elements across blocks in dp1 and dp2. We use this
  161. 			information together with cntA and cnt array to calculate the
  162. 			updated frequency of the element. As in brute force solution above,
  163. 			the idea is to first remove the contribution of frequency in 
  164. 			frequency of frequency table, add the elements and then update the
  165. 			tables.
  166. 			*/
  167. 			for(int i = 1; x * L - i >= l; i++) {
  168. 				if(dp1[x][y][i] + cntA[a[x * L - i]] > 0) 
  169. 					cnt[x][y][dp1[x][y][i] + cntA[a[x * L - i]]]--;
  170. 				cntA[a[x * L - i]]++;
  171. 				cnt[x][y][dp1[x][y][i] + cntA[a[x * L - i]]]++;
  172.  
  173. 			}
  174. 			for(int i = 1; (y + 1) * L + i - 1 <= r; i++) {
  175. 				if(dp2[x][y][i] + cntA[a[(y + 1) * L + i - 1]] > 0) 
  176. 					cnt[x][y][dp2[x][y][i] + cntA[a[(y + 1) * L + i - 1]]]--;
  177. 				cntA[a[(y + 1) * L + i - 1]]++;
  178. 				cnt[x][y][dp2[x][y][i] + cntA[a[(y + 1) * L + i - 1]]]++;
  179. 			}
  180.  
  181. 			/*
  182. 			Calculate the mex of the frequency. Idea is again same as above brute
  183. 			force. See above for details. Just that instead of cntCnt,
  184. 			information is stored in cnt.
  185. 			*/
  186. 			for(int i = 1; ; i++) {
  187. 				if(cnt[x][y][i] == 0) {
  188. 					prev_ans = i;
  189. 					break;	
  190. 				}
  191. 			}
  192.  
  193. 			/*
  194. 			Bring back the arrays to original state. Again copy pasting of code
  195. 			in reverse order :P. See above brute force for details.
  196. 			*/
  197. 			for(int i = 1; x * L - i >= l; i++) {
  198. 				cnt[x][y][dp1[x][y][i] + cntA[a[x * L - i]]]--;
  199. 				cntA[a[x * L - i]]--;
  200. 				if(dp1[x][y][i] + cntA[a[x * L - i]] > 0) 
  201. 					cnt[x][y][dp1[x][y][i] + cntA[a[x * L - i]]]++;
  202.  
  203. 			}
  204. 			for(int i = 1; (y + 1) * L + i - 1 <= r; i++) { 
  205. 				cnt[x][y][dp2[x][y][i] + cntA[a[(y + 1) * L + i - 1]]]--;
  206. 				cntA[a[(y + 1) * L + i - 1]]--;
  207. 				if(dp2[x][y][i] + cntA[a[(y + 1) * L + i - 1]] > 0)
  208. 					cnt[x][y][dp2[x][y][i] + cntA[a[(y + 1) * L + i - 1]]]++;
  209. 			}
  210. 		}
  211. 		// Print the answer.
  212. 		cout << prev_ans << "\n";
  213. 	}
  214. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
10 3
1 1 2 3 4 2 3 3 1 5
1 10
5 1
11 9
stdout
copy 
4
3
2
https://ideone.com/8sxhBR
language:
C++14 (gcc 8.3)
created:
5 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!