Getting tle for 2 cases

#1


I have got tle due to sorting of vector…But i am not able to set the boolena function in logn comlexity …binary search requires sorted array which is only min_heap or set…But how to use them here

#2

We can solve this problem using a trie data structure. At each node of the trie, we will store the ith bit of the number for a query of type 0. To solve the query of type 1 we will store the indexes of the number that pass through that node. When we go down the tree during a query and maximizing the xor, we go in a direction that contains at least one index in range L to R, otherwise we ,go in the other direction. To search if at least one index is within the stored indexes we will use binary search.
Hope this helps.

#3

how to store the indexes in sorted order and iterate over them for binary sort…is my question

#4

Since the indices will always be positive, you can apply count sort on them. That will do your work in linear time.

#5

Thanks…got the code submitted. Rather i applied linear search on unsorted array.

1 Like
#6

That is even better, to be honest.
I’d request you to mark the doubt as resolved.
Thank you.