PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
BINARY SEARCH, TRIES, SEGMENT TREES
PROBLEM:
Given Q queries (l, r, x), find the maximum value of a_{j} \otimes x where l \le j \le r.
EXPLANATION:
The first subtask is trivial : You can just iterate through all elements in range for each query to find the answer.
The third subtask has x = 0, which reduces the problem to Range Maximum Query, which can be solved with Sparse Table or Segment Trees in O(n\log n).
Now, let’s see how to solve the second subtask. One way to solve this is by building a trie (though it’s not neccesary and the same solution can be applied to the sorted array of numbers instead). Build a trie for all the numbers in range [l, r]. We walk down the trie from the root. Whenever we have a choice of whether to go left or right, we pick the choice that maximizes the final xor value, i.e. if the current bit of x is 0, choose the path that is labelled 1 and vice versa. Thus, each query can now be solved in O(\log n) time.
We can generalize this idea to solve the whole problem. What we need here is a segment tree of tries (or segment tree of sorted arrays is sufficient in this case). We can build a trie for each segment of the segment tree in O(n\log n\log a_{i}) time and for each query, we need to query the trie in O(\log n) segments. Thus, the whole solution would work in O((n + q)\log n\log a_{i}) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.