Here is the problem.

So basically you have an array of integers a[] of size n.

n <  = 1e5 and a[i] <  = 2¹⁵ ( = 3, 2 * 10⁴).

And you're given q <  = 5e4 queries of the form (x, l, r) for which the answer is the maximum value of x xor a[i] for l <  = i <  = r.

The editorial's solution is about persistent segment trees which I know nothing about.Before reading that I was trying to solve it using MO's algorithm + trie which has a complexity of O((n + q) * sqrt(n)) without counting the time to answer a query using the trie.Now q * sqrt(n) is fine but n * sqrt(n) is too much.Because n * sqrt(n) is caused by the movement of r to the right(which can reach n) I thought, is it possible to use the fact that all the numbers are <= 2¹⁵ to improve the complexity?

If r moves to the right more than 2¹⁵ times then at least one element is repeated right?

Is it possible to use this(or any other optimization) to get MO's algorithm to pass?

Here is my code.It passes 11 test cases out of 14 and the rest are getting TLE(actually it says segmentation fault but I think it's TLE).

Any other solution is welcome.

Thanks !