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

*n* < = 1*e*5 and *a*[*i*] < = 2^{15} ( = 3, 2 * 10^{4}).

And you're given *q* < = 5*e*4 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^{15} to improve the complexity?

If *r* moves to the right more than 2^{15} 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 !

you can try to speed up MO's a little by sorting the endings ascending if block id is odd and descending otherwise this will make MO's algorithm take about half the time.

Thanks.

I added this but now the solution only passes 10 test cases, and the four others got TLE.

oh! it seems time was not the problem there is a problem with line 137 (deleting some thing before you add it) I resubmitted your code with only rewrite this line after add lines and it gives AC

Thanks a lot, this really fixed it! (turns out it was segmentation fault after all)

The correct ordering should be:

I find this strange because I always thought the ordering with MO's is "remove add add remove", I remember I passed some problems with it too..

Also, isn't my solution's complexity too high to get accepted? I know the time limit isn't visible but I think it's too high!

Anyways, it's okay now.Problem solved.

It's always better to add before remove because removing first may cause some problems as we see here. the complexity is higher than the intended solution ofcourse but it seems that it's enough for MO's even without the speed up I talked about before.

The

`/`

operator is too costly. Try pre-calculating`blc[i] = i / block`

and use that in compare function. Hope it'll pass (but there exists quasi-linear solution).Might be faster (I don't know if GCC optimizes the above loop):

Thanks.

Actually time was not the problem, as was mentioned here.