fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. typedef pair<int,int>pp;
  4. #define N 500002
  5. #define Q 500002
  6. int INF = (1 << 30) + 7;
  7.  
  8. int n,m,q; 
  9. int suff[N], a[N]; 
  10. pp queries[Q];
  11. int bestInterval[N];
  12. int whereInSegment[Q];
  13. int st[N * 10], lazy[N * 10];
  14.  
  15.  
  16. struct Event {
  17. 	int type, idx, pos; 
  18. 	Event(int type = 0, int idx = 0, int pos = 0) : type(type), idx(idx), pos(pos) {}
  19. 	bool operator <(const Event&x) const {
  20. 		if (pos != x.pos) return pos < x.pos; 
  21. 		return type < x.type;
  22. 	}
  23. };
  24.  
  25. struct trie {
  26. 	trie* a[2]; 
  27. 	int cnt, minIndex;
  28. 	trie() { 
  29. 		memset(a,0,sizeof a); 
  30. 		cnt = 0, minIndex = INF;
  31. 	} 
  32.  
  33. 	void insert(int x, int &index,  int i = 29) {
  34. 		cnt++; minIndex = index;
  35. 		if (i == -1) { return ;  }
  36. 		int bit = (x & (1 << i))  != 0;
  37. 		if (a[bit] == 0) a[bit] = new trie(); 
  38. 		a[bit]->insert(x, index, i - 1);
  39. 	}
  40.  
  41. 	int query(int x, int i = 29, bool isBigger = false) {
  42. 		if (i == -1) {  return minIndex;  }
  43. 		int bit = (x & (1 << i)) != 0;
  44. 		int mbit = (m & (1 << i)) != 0;
  45. 		if (isBigger) {
  46. 			trie*best = new trie(); if (a[0]) best = a[0]; 
  47. 			if (a[1] && a[1]->minIndex < best->minIndex) best = a[1];
  48. 			return best->query(x, i - 1, true);
  49. 		} else {
  50. 			if (mbit == 0) {
  51. 				int c1 = -1, c2 = -1;
  52. 				if (bit == 0) {
  53. 					if (a[0]) c1 = a[0]->query(x, i - 1, false); 
  54. 					if (a[1]) c2 = a[1]->query(x, i - 1, true); 
  55. 				} else {
  56. 					if (a[0]) c1 = a[0]->query(x, i - 1, true); 
  57. 					if (a[1]) c2 = a[1]->query(x, i - 1, false); 
  58. 				}
  59. 				if (c1 == -1 && c2 == -1) return -1;
  60. 				else if (c1 != -1 && c2 != -1) return min(c1,c2); 
  61. 				else if (c1 != -1) return c1; 
  62. 				else return c2; 
  63. 			} else {
  64. 				if (bit == 0) {
  65. 					if (a[1] == 0) return -1; 
  66. 					return a[1]->query(x, i - 1, false);
  67. 				} else {
  68. 					if (a[0] == 0) return -1; 
  69. 					return a[0]->query(x, i - 1, false);
  70. 				}
  71. 			}
  72. 		}
  73. 	}
  74.  
  75. 	void clear() {
  76. 		for(int i=0; i<2; i++) {
  77. 			if (a[i]) a[i]->clear(); 
  78. 			delete a[i]; 
  79. 			a[i] = 0;
  80. 		}
  81. 	}
  82. };
  83.  
  84. //*******SEGMENT TREE ************
  85. void pushLazy(int p, int l, int r) {
  86. 	if (lazy[p] != INF) {
  87. 		if (l != r) {
  88. 			lazy[p*2] = min(lazy[p], lazy[p*2]);
  89. 			lazy[p*2+1] = min(lazy[p], lazy[p*2+1]);
  90. 		}
  91. 		st[p] = min(st[p], lazy[p]);
  92. 		lazy[p] = INF;
  93. 	}
  94. }
  95.  
  96. void build(int p =1 , int l = 1, int r = q) {
  97. 	lazy[p] = INF;
  98. 	if (l == r) { st[p] = INF; return ; } 
  99. 	int mid = (l+r) >> 1; 
  100. 	build(p*2, l, mid);
  101. 	build(p*2+1,mid+1,r); 	
  102. 	st[p] = INF;
  103. }
  104.  
  105. void update(int i, int j, int val, int type, int p = 1, int l = 1, int r = q) {
  106. 	pushLazy(p, l, r);
  107. 	if (i > r || j < l) return ; 
  108. 	if (i <= l && j >= r) { 
  109. 		if (type == 0) st[p] = val; 
  110. 		else lazy[p] = val, pushLazy(p, l, r); 
  111. 		return ;
  112. 	}
  113. 	int mid = (l+r) >> 1; 
  114. 	update(i, j, val, type, p*2, l, mid); 
  115. 	update(i, j, val, type, p*2+1, mid+1, r); 
  116. 	st[p] = min(st[p*2], st[p*2+1]); 
  117. }
  118.  
  119. int query(int i, int p = 1, int l = 1, int r = q) {
  120. 	pushLazy(p, l, r);
  121. 	if (i > r || i < l) return INF; 
  122. 	if (l == r) { return st[p]; } 
  123. 	int mid = (l+r) >> 1; 
  124. 	return min(query(i, p * 2, l, mid), query(i, p*2+1, mid+1, r)); 
  125. }
  126.  
  127. //******************************
  128.  
  129. void solveTrie() {
  130. 	trie* tr = new trie(); 
  131. 	for(int i=n; i>=1; i--) {
  132. 		tr->insert(suff[i + 1], i); 
  133. 		bestInterval[i] = tr->query(suff[i]); 
  134. 	}
  135. }
  136.  
  137. int main() {
  138. 	int t; scanf("%d", &t); 
  139. 	while(t--) {
  140. 		scanf("%d%d%d", &n,&m,&q); 
  141. 		for(int i=1; i<=n; i++) scanf("%d", &a[i]);
  142. 		suff[n + 1] = 0;
  143. 		for(int i=n; i>=1; i--) suff[i] = suff[i + 1] ^ a[i];
  144. 		vector<pp> ends;
  145. 		for(int i=1; i<=q; i++) {
  146. 			scanf("%d%d", &queries[i].first, &queries[i].second);
  147. 			ends.push_back(make_pair(queries[i].second, i));
  148. 		}
  149. 		sort(ends.begin(), ends.end()); 
  150. 		for(int i=0; i<(int)ends.size(); i++) whereInSegment[ends[i].second] = i + 1; 
  151.  
  152. 		build();
  153. 		solveTrie();
  154.  
  155. 		vector<Event> sweep; 
  156. 		for(int i=1; i<=n; i++) sweep.push_back(Event(1, i, i));
  157. 		for(int i=1; i<=q; i++) {
  158. 			sweep.push_back(Event(0, i, queries[i].first)); 
  159. 		}
  160. 		sort(sweep.begin(), sweep.end()); 
  161. 		for(int i=0; i<(int)sweep.size(); i++) {
  162. 			Event cur = sweep[i];
  163. 			if (cur.type == 0) {
  164. 				update(whereInSegment[cur.idx], whereInSegment[cur.idx], INF , 0); 
  165. 			} else if (cur.type == 1) {
  166. 				if (bestInterval[cur.idx] != -1) {
  167. 					int from = lower_bound(ends.begin(), ends.end(), make_pair(bestInterval[cur.idx], -1)) - ends.begin() + 1; 
  168. 					update(from, q, bestInterval[cur.idx] - cur.idx + 1, 1);
  169. 				}
  170. 			} else assert(0);
  171. 		}
  172.  
  173. 		for(int i=1; i<=q; i++) {
  174.  
  175. 			int res = query(whereInSegment[i]); if (res == INF) res = -1;
  176. 			printf("%d\n", res);
  177. 		}
  178.  
  179.  
  180. 	}
  181. 	return 0;
  182. }
Success #stdin #stdout 0s 66816KB
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/65wGW2
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!