fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int n, m, q;
  6. int a[500100];
  7. int best[500100];
  8. int seg[5001000];
  9. int lazy[5001000];
  10. int sq[500100];
  11. int eq[500100];
  12. vector<pair<int, int> > qrs;
  13. vector<pair<int, int> > sweep;
  14.  
  15. const int MAX_CHAR = 2;
  16. struct trie {
  17. 	trie* child[MAX_CHAR];
  18. 	int maxi;
  19.  
  20. 	trie() {
  21. 		memset(child, 0, sizeof(child));
  22. 		maxi = -1;
  23. 	}
  24.  
  25. 	void insert(int a, int idx, int length = 30){
  26. 		maxi = max(maxi, idx);
  27. 		if (length == -1) return;
  28.  
  29. 		int d = a / (1 << length);
  30. 		if (child[d] == 0) child[d] = new trie();
  31. 		child[d]->insert(a % (1 << length), idx, length - 1);
  32. 	}
  33.  
  34. 	int query(int a, int length = 30){
  35. 		if (length == -1) return maxi;
  36.  
  37. 		int d = a / (1 << length);
  38. 		int dm = (m % (1 << (length + 1))) / (1 << length);
  39. 		int ans = -1;
  40. 		if (dm == 0 && child[1 - d] != 0) ans = child[1 - d]->maxi;
  41. 		if (dm == 0 && child[d] != 0) ans = max(ans, child[d]->query(a % (1 << length), length - 1));
  42. 		else if (dm == 1 && child[1 - d] != 0) ans = max(ans, child[1 - d]->query(a % (1 << length), length - 1));
  43. 		return ans;
  44. 	}
  45. };
  46.  
  47. void init(trie *cur)
  48. {
  49. 	if(cur == 0) return;
  50. 	for (int i = 0; i < MAX_CHAR; i++)
  51. 	if (cur->child[i] != NULL)
  52. 		init(cur->child[i]);
  53. 	delete cur;
  54. }
  55.  
  56. void clear(){
  57. 	for (int i = 0; i <= n; i++) best[i] = 1e9;
  58. 	for (int i = 0; i <= q * 5; i++) seg[i] = -1, lazy[i] = 1e9;
  59. 	sweep.clear();
  60. 	qrs.clear();
  61. }
  62.  
  63. void pushLazy(int p){
  64. 	if (lazy[p] != 1e9){
  65. 		lazy[p * 2] = min(lazy[p * 2], lazy[p]);
  66. 		lazy[p * 2 + 1] = min(lazy[p * 2 + 1], lazy[p]);
  67. 		seg[p] = min(seg[p], lazy[p]);
  68. 		lazy[p] = 1e9;
  69. 	}
  70. }
  71.  
  72. void update(int i, int j, int val, int p = 1, int L = 0, int R = q - 1){
  73. 	pushLazy(p);
  74. 	if (i > R || j < L) return;
  75. 	if (L >= i && R <= j){
  76. 		lazy[p] = val;
  77. 		pushLazy(p);
  78. 		return;
  79. 	}
  80.  
  81. 	int midi = (L + R) / 2;
  82. 	update(i, j, val, p * 2, L, midi);
  83. 	update(i, j, val, p * 2 + 1, midi + 1, R);
  84. 	seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
  85. }
  86.  
  87. void turnOn(int i, int p = 1, int L = 0, int R = q - 1){
  88. 	pushLazy(p);
  89. 	if (L == R){
  90. 		seg[p] = 1e9;
  91. 		return;
  92. 	}
  93.  
  94. 	int midi = (L + R) / 2;
  95. 	if (i <= midi) turnOn(i, p * 2, L, midi);
  96. 	else turnOn(i, p * 2 + 1, midi + 1, R);
  97. 	seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
  98. }
  99.  
  100. int query(int i, int p = 1, int L = 0, int R = q - 1){
  101. 	pushLazy(p);
  102. 	if (L == R) return seg[p];
  103.  
  104. 	int midi = (L + R) / 2;
  105. 	if (i <= midi) return query(i, p * 2, L, midi);
  106. 	return query(i, p * 2 + 1, midi + 1, R);
  107. }
  108.  
  109. void calcBest(){
  110. 	trie* root = new trie();
  111. 	root->insert(a[0], 0);
  112. 	for (int i = 1; i <= n; i++){
  113. 		int s = root->query(a[i]);
  114. 		if(s != -1) best[s + 1] = min(i, best[s + 1]);
  115. 		root->insert(a[i], i);
  116. 	}
  117. 	init(root);
  118. }
  119.  
  120. void calcSweep(){
  121. 	for (int i = 0; i < (int)sweep.size(); i++){
  122. 		int fir = sweep[i].first, sec = sweep[i].second;
  123. 		if (sec != 1e9){
  124. 			int idx = lower_bound(qrs.begin(), qrs.end(), make_pair(sec, fir)) - qrs.begin();
  125. 			turnOn(idx);
  126. 		}
  127. 		else{
  128. 			if (best[fir] == 1e9) continue;
  129. 			int length = best[fir] - fir + 1;
  130. 			int idx = lower_bound(qrs.begin(), qrs.end(), make_pair(best[fir], -1)) - qrs.begin();
  131. 			update(idx, q - 1, length);
  132. 		}
  133. 	}
  134. }
  135.  
  136. int main() {
  137.  
  138. 	int t; 
  139. 	scanf("%d",&t);
  140. 	while (t--){
  141. 		scanf("%d %d %d",&n,&m,&q);
  142. 		clear();
  143. 		for (int i = 1; i <= n; i++) cin >> a[i];
  144. 		for (int i = 1; i <= n; i++) a[i] ^= a[i - 1];
  145. 		calcBest();
  146. 		for (int i = 0; i < q; i++){
  147. 			scanf("%d %d",sq+i,eq+i);
  148. 			qrs.push_back(make_pair(eq[i], sq[i]));
  149. 			sweep.push_back(make_pair(sq[i], eq[i]));
  150. 		}
  151. 		for (int i = 1; i <= n; i++) sweep.push_back(make_pair(i, 1e9));
  152. 		sort(sweep.begin(), sweep.end());
  153. 		sort(qrs.begin(), qrs.end());
  154. 		calcSweep();
  155. 		for (int i = 0; i < q; i++){
  156. 			int idx = lower_bound(qrs.begin(), qrs.end(), make_pair(eq[i], sq[i])) - qrs.begin();
  157. 			int ans = query(idx);
  158. 			if (ans > 1e8) ans = -1;
  159. 			printf("%d\n",ans);
  160. 		}
  161. 	}
  162.  
  163. 	return 0;
  164. }
Success #stdin #stdout 0s 62136KB
comments (?)
stdin
copy 
2
3 7 2
1 2 4
1 3
2 3
3 3 3
1 2 3
1 2
1 3
2 2
stdout
copy 
3
-1
2
1
-1
https://ideone.com/iTVEwK
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!