fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. #define int long long
  5.  
  6. using namespace std;
  7. const int MAXN = (1 << 18);
  8. const int ALPH = 26;
  9. const int CNTBITS = 31;
  10. const int inf = (int)1e16 + 42;
  11.  
  12. struct node_trie
  13. {
  14. 	int cnt;
  15. 	node_trie *next[ALPH];
  16. 	node_trie() {cnt = 0; for(int i = 0; i < ALPH; i++) next[i] = NULL;}
  17. };
  18.  
  19. string to_bin(int x)
  20. {
  21. 	string add_word = "";
  22. 	for(int bit = CNTBITS; bit >= 0; bit--)
  23. 		add_word += (char)(((x >> bit) & 1ll) + '0');
  24.  
  25. 	return add_word;
  26. }
  27.  
  28. struct trie
  29. {
  30.  
  31. 	node_trie *root;
  32. 	string add_word;
  33.  
  34. 	trie() {root = new node_trie();}
  35.  
  36. 	void add(int p, node_trie* curr)
  37. 	{
  38. 		if(p == add_word.size())
  39. 		{
  40. 			curr->cnt++;
  41. 			return;
  42. 		}
  43.  
  44. 		if(curr->next[add_word[p] - '0'] == NULL)
  45. 			curr->next[add_word[p] - '0'] = new node_trie();
  46.  
  47. 		add(p + 1, curr->next[add_word[p] - '0']);
  48. 		curr->cnt++;
  49. 	}
  50.  
  51. 	void del(int p, node_trie* curr)
  52. 	{
  53. 		if(p == add_word.size())
  54. 		{
  55. 			if(curr->cnt) curr->cnt--;
  56. 			return;
  57. 		}
  58.  
  59. 		if(curr->next[add_word[p] - '0'] == NULL) return;
  60. 		del(p + 1, curr->next[add_word[p] - '0']);
  61. 		curr->cnt--;
  62. 	}
  63.  
  64. 	int find(int p, node_trie* curr)
  65. 	{
  66. 		if(p == add_word.size())
  67. 			return curr->cnt;
  68.  
  69. 		if(curr->next[add_word[p] - '0'] == NULL) return -1;
  70. 		return find(p + 1, curr->next[add_word[p] - '0']);
  71. 	}   
  72.  
  73. 	int opposite(int p, node_trie* curr)
  74. 	{
  75. 		if(p == add_word.size())
  76. 			return 0;
  77.  
  78. 		int bit = (add_word[p] - '0') ^ 1;
  79. 		if(curr->next[bit ^ 1] == NULL || curr->next[bit ^ 1]->cnt == 0) 
  80. 			if(curr->next[bit] != NULL && curr->next[bit]->cnt != 0) 
  81. 				return (1 << (CNTBITS - p)) + opposite(p + 1, curr->next[bit]); 
  82. 			else return inf;
  83.  
  84. 		return opposite(p + 1, curr->next[bit ^ 1]);
  85. 	}
  86.  
  87. 	void add(string s)
  88. 	{
  89. 		add_word = s;
  90. 		add(0, root);
  91. 	}
  92.  
  93. 	void del(string s)
  94. 	{	
  95. 		add_word = s;
  96. 		del(0, root);
  97. 	}
  98.  
  99. 	int find(string s)
  100. 	{
  101. 		add_word = s;
  102. 		return find(0, root);
  103. 	}
  104.  
  105. 	int minxor(string x)
  106. 	{	
  107. 		add_word = x;
  108. 		return opposite(0, root);
  109. 	}	
  110. };	
  111.  
  112. int ans[MAXN];
  113.  
  114. struct segment_tree
  115. {
  116. 	trie t;
  117. 	vector<int> tr[4 * MAXN];
  118.  
  119. 	void insert(int qL, int qR, int val, int l, int r, int idx)
  120. 	{
  121. 		if(qL <= l && r <= qR)
  122. 		{
  123. 			tr[idx].push_back(val);
  124. 			return;
  125. 		}
  126.  
  127. 		if(qL > r || l > qR)
  128. 			return;
  129.  
  130. 		int mid = (l + r) >> 1;
  131. 		insert(qL, qR, val, l, mid, 2 * idx + 1);
  132. 		insert(qL, qR, val, mid + 1, r, 2 * idx + 2);
  133. 	}
  134.  
  135. 	void dfs(int res, int l, int r, int idx)
  136. 	{
  137. 		int newres = res;
  138. 		for(int i = 0; i < tr[idx].size(); i++)
  139. 		{
  140. 			newres = min(newres, t.minxor(to_bin(tr[idx][i])));
  141. 			t.add(to_bin(tr[idx][i]));
  142. 		}
  143.  
  144. 		if(l == r) ans[l] = newres;
  145.  
  146. 		int mid = (l + r) >> 1;
  147. 		if(l != r) dfs(newres, l, mid, 2 * idx + 1);
  148. 		if(l != r) dfs(newres, mid + 1, r, 2 * idx + 2);
  149.  
  150. 		for(int i = 0; i < tr[idx].size(); i++)
  151. 			t.del(to_bin(tr[idx][i]));
  152. 	}	
  153. };
  154.  
  155. int m;
  156. map<int, int> last;
  157. bool req[MAXN];
  158. vector<pair<int, pair<int, int> > > q; 
  159.  
  160. void read()
  161. {
  162. 	cin >> m;
  163.  
  164. 	for(int i = 1; i <= m; i++)
  165. 	{
  166. 		int type;
  167. 		cin >> type;
  168.  
  169. 		if(type == 1)
  170. 		{
  171. 			int val;
  172. 			cin >> val;
  173. 			last[val] = i;
  174. 		}
  175. 		else if(type == 2)
  176. 		{
  177. 			int val;
  178. 			cin >> val;
  179. 			q.push_back(make_pair(val, make_pair(last[val], i)));
  180. 			last[val] = 0;
  181. 		}
  182. 		else req[i] = true;
  183. 	}	
  184. }
  185.  
  186. segment_tree t;
  187.  
  188. void solve()
  189. {
  190. 	for(map<int, int>::iterator it = last.begin(); it != last.end(); ++it)
  191. 		if(it->second != 0) 
  192. 			q.push_back(make_pair(it->first, make_pair(it->second, m)));
  193.  
  194. 	for(int i = 0; i < q.size(); i++)
  195. 		t.insert(q[i].second.first, q[i].second.second, q[i].first, 1, m, 0);
  196.  
  197. 	t.dfs(inf, 1, m, 0);
  198.  
  199. 	for(int i = 1; i <= m; i++)
  200. 		if(req[i]) cout << ans[i] << endl;
  201. }
  202.  
  203. #undef int
  204. int main()
  205. {
  206. 	ios_base::sync_with_stdio(false);
  207. 	cin.tie(NULL);
  208.  
  209. 	read();
  210. 	solve();
  211. 	return 0;
  212. }
  213.  
  214.  
Runtime error #stdin #stdout 0s 18080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pGncme
language:
C++14 (gcc 8.3)
created:
8 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!