Hello!
I was solving problem Minxor from second day of RMI 2014. In short the problem is:
You have 3 types of queries.
1 x -> inserts x into the set
2 x -> deletes x from the set
3 -> asks for the smallest xor of any two numbers in the set
I solved the problem offline using a trie + divide and conquer. My solution is similar to link. Again in short: compressing all updates as "number x appears from time I to time J". Here is the code. The complexity is O(M * log(M) * 32);
So my question is:
Is there a solution which runs faster than that or/is online. Thanks in advance :)
Yes, there's a simpler, online, O(log M) per query solution. Notice that if a < b < c, the minimum xor pair is never (a, c).
Can you explain a little bit more the idea? How we get that (log M) per query ?
Using the observation above, you can prove that members of the minimum xor pair must be adjacent in sorted order. So you only need to keep a simple BST (such as a STL set<>) to keep track of successors and predecessors of inserted/deleted elements and another min-heap-like structure in which you actually store the adjacent xor values in increasing order.
Thats a nice trick! Thanks
BTW is there a similar trick but for maximum xor?