982. The Best XOR When the Partner Is Capped
You are given n values, then q queries. Each query is a pair x m. Print the
largest x XOR a[i] over the values with a[i] <= m, or -1 if no value is at
most m.
``` values 0 1 2 x=3 m=1 -> 3 only 0 and 1 are allowed, and 3 xor 0 is 3 x=1 m=3 -> 3 everything is allowed, and 1 xor 2 is 3 x=5 m=6 -> 7 5 xor 2
values 5 9 x=6 m=4 -> -1 nothing is at most 4 x=6 m=5 -> 3 only 5 is allowed ```
## Why the cap cannot be checked during the walk
The greedy of problem 973 chooses a branch by the bit it holds, and the cap is a
statement about the whole VALUE. A subtree can contain values on both sides of
m, so "this branch is allowed" is not a question the trie can answer at a
node, and pruning by it during the descent is wrong in a way that passes small
tests.
Carrying the cap through the walk properly is possible but fiddly. There is a much simpler route.
## Answer the queries in a different order from the one they arrive in
The set of allowed values grows with m and never shrinks. So:
sort the values ascending
sort the queries by m ascending, remembering each one original position
k = 0
for each query (m, x) in that order:
while k < n and a[k] <= m: insert a[k] into the trie; k = k + 1
answer = -1 if nothing has been inserted else bestXorAgainstTrie(x)
store the answer at the query original position
print the answers in the original order
Each value is inserted exactly once across the whole run, because k only moves
forward. That is what makes this O(30 (n + q)) rather than one trie per query.
This is offline processing: the queries are all known in advance, so they may be answered in whatever order is convenient, as long as the answers are put back where they belong. A problem that had to answer each query before seeing the next could not do this.
## Why the pointer never has to go back
The queries are processed in increasing m, and a value inserted for one query
is at most that m, so it is at most every later m too. Nothing ever becomes
disallowed, so nothing is ever removed and the trie needs no counters.
## The two things that go wrong
Forgetting to restore the ORIGINAL order prints the right answers against the wrong queries. Keeping the original index alongside each sorted query, and writing into an answer array indexed by it, is the fix.
An empty trie must give -1, and the test is whether anything has been inserted
yet, not whether the root has children. Once one insertion has happened the root
always has a child, so the two tests differ exactly on the queries that need the
-1.
## Overflow
Nothing here overflows. Every value, cap, query and answer is below
2^30 = 1073741824, inside the 2147483647 limit of a signed 32 bit integer.
## Cost
Sorting is O(n log n + q log q). The sweep inserts each value once and answers
each query in 30 steps, so O(30 (n + q)). Space is at most
1 + 30 n = 3000001 nodes plus the query array.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `0 ≤ each value, each x and each m ≤ 1073741823`, which is `2^30 - 1` - Values may repeat.
Input
The first line contains an integer n.
The second line contains n integers.
The third line contains an integer q.
Each of the next q lines contains two integers x and m, separated by a
space.
Output
For each query, in the order the queries were given, print one integer on its own line: the largest XOR of x with a value that is at most m, or -1 if no value is at most m.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.