Here is a different approach for an online solution - (solved in Java btw):
Needed info:
- persistent segment tree
- “sparse” segment tree - if an interval has no value > 0 then the no need for the subtrees
- reuse the memory allocated in previous tests
So basically keep a persistent “sparse” segment tree of numbers 0 … 10^9 to keep track of all the numbers present from the root to the specific node. When a query is done we just have to ask in the persistent seg tree of the node the xor value for the interval [0, K].
The query time is O(log(M)) where M is the 10^9.
First implementation gave TLE and after some debugging I’ve noticed that queries where “peanuts” compared to the build of the date structure. As we all know Java is “good” that you do not have to handle the memory but unfortunately the allocation and GC internally could be a pain in the ass.
So the thing done in order to pass was to allocated from the beginning the maximum nodes that can be used for a test case = O(Nlog(M)* which is at most - 30 * 100 000 --> 3 * 10^6.
Also in the following tests will reuse the same nodes.
Hope this will save to others the time I’ve lost investigating.
Link to my solution.