fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Node{
  5. 	public:
  6. 	Node* left;
  7. 	Node* right;
  8. };
  9.  
  10. class trie{
  11. 	Node* root;
  12. 	public:
  13. 	trie(){
  14. 		root = new Node();
  15. 	}
  16. 	void insert(int n){
  17. 		Node*temp = root;
  18. 		for(int i = 31; i >= 0; i--)
  19. 		{
  20. 			int bit = (n>>i)&1;
  21. 			if(bit == 0)
  22. 			{
  23. 				if(temp->left == NULL)
  24. 				{
  25. 					temp->left = new Node();
  26. 				}
  27. 				temp = temp->left;
  28. 			}
  29. 			else
  30. 			{
  31. 				if(temp->right == NULL)
  32. 				{
  33. 					temp->right = new Node();
  34. 				}
  35. 				temp = temp->right;
  36. 			}
  37. 		}
  38. 	}
  39. 	int max_helper(int x){
  40. 		Node* temp = root;
  41. 		int current_ans = 0;
  42. 		for(int i = 31; i >= 0; i--)
  43. 		{
  44. 			int bit = (x>>i)&1;
  45. 			if(bit == 0)
  46. 			{
  47. 				//search for the compliment bit
  48. 				if(temp->right == NULL)temp = temp->left;
  49. 				else{
  50. 					current_ans += (1 << i);
  51. 					temp = temp->right;
  52. 				}
  53. 			}
  54. 			else{
  55. 				//serach for the bit 1
  56. 				if(temp->left == NULL)temp = temp->right;
  57. 				else{
  58. 					current_ans += (1<<i);
  59. 					temp = temp->left;
  60. 				}
  61. 			}
  62. 		}
  63. 		return current_ans;
  64. 	}
  65. 	int max_function(int* arr, int l, int r, int x)
  66. 	{
  67. 		int real_ans = 0;
  68. 		int ans = 0;
  69. 		for(int i = l; i <= r; i++)
  70. 		{
  71. 			int inp =  arr[i];
  72. 			insert(inp);
  73. 			int inter = max_helper(x);
  74. 			ans = max(ans, inter);
  75. 		}
  76. 		real_ans = (ans^x);
  77. 		return real_ans;
  78. 	}
  79. };
  80.  
  81. int main()
  82. {
  83. 	int arr[100005] = {0};
  84. 	trie tr;
  85. 	int q;cin >> q;int i = 1;
  86. 	while(q--){
  87. 		int type;
  88. 		cin >> type;
  89. 		if(!type){
  90. 			//int n;
  91. 			cin >> arr[i];//tr.insert(n);
  92. 			//arr[i] = n;
  93. 			i++;
  94. 		}
  95. 		else{
  96. 			int l, r, x;
  97. 			cin >> l >> r >> x;
  98. 			cout << tr.max_function(arr, l, r, x) << endl;
  99. 		}
  100. 	}
  101. 	return 0;
  102. }
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
5
0 3 
0 5
0 10 
0 6 
1 1 4 6
stdout
copy 
10
https://ideone.com/5f1X47
Trie: Range xor
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!