Maximum Xor Query
All submissions for this problem are available.
Today, Flippy the bird came up with a simple problem. You have an array a of nonnegative integers. There are q queries that has to be answered. The i-th query is denoted by three positive integers, li, ri and xi. For each query, you should output the maximum possible value of xi xor aj, where l ≤ j ≤ r.
You may learn about the xor operator here : https://en.wikipedia.org/wiki/Exclusive_or (see the part which explains xor on integers)
The first line contains a single integer n, the length of the array. The next line contains n space-seperated integers, denoting the elements of a. The next line contains a single integer q, denoting the number of queries. The next q lines contain three space-seperated integers each, denoting li, ri and xi.
For each query, output its answer on a single line.
- 1 ≤ n ≤ 300000
- 1 ≤ q ≤ 100000
- 1 ≤ li ≤ ri ≤ n
- 1 ≤ xi,ai ≤ 1000000
- Subtask 1 (14 points) : 1 ≤ n, q ≤ 3000
- Subtask 2 (20 points) : li = L and ri = R for all i for some fixed values L and R.
- Subtask 3 (23 points) : xi = 0 for all i
- Subtask 4 (43 points) : Original Constraints
Input: 5 2 3 6 4 7 3 2 4 6 1 5 1 3 3 6 Output: 5 7 0
Example case. For the first query, 3 xor 6 = 5 yields the maximum value. For the second query, 6 xor 1 = 7 yields the maximum value. For the third query, 6 xor 6 = 0 is the only possibility and thus yields the maximum value.
|Tags||easy-medium, segment-tree, trie, zscoder|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.