PROBLEM LINK:
Author: Fedor Korobeinikov
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM-HARD
PRE-REQUISITES:
Tutorial on trie and example problems
PROBLEM:
Given an initially empty integer array (1-indexed) and M queries:
- Type 0: Add the integer number x at the end of the array.
- Type 1: On the interval L..R find a number y, to maximize (x xor y).
- Type 2: Delete last k numbers in the array
- Type 3: On the interval L..R, count the number of integers less than or equal to x.
- Type 4: On the interval L..R, find the k_{th} smallest integer (k_{th} order statistic).
QUICK EXPLANATION:
Make a trie of integers experessed in binary and at each node in trie, also store the indexes of numbers which pass through that node.
EXPLANATION:
If you donāt know about tries, read the complete post given in pre-requisites and try to implement those problems.
Letās say in query of Type 1, L=1 and R=N, how will we solve?
Weāll build a trie and we can insert in O(number of bits) each element. We can also delete in O(number of bits) any number, but weāll have to store at each node count of elements passing through that node. The following image doesnāt store counts at node.
For maximum xor query, for L=1 and R=N, weāll just traverse over the whole trie and starting from most significant bit(MSB), we try to form largest number possible. Example:
But our query is for range L to R, so we store at each node also the indexes of numbers which pass through the that node. For example:
But how does this help?
When we go down the tree during a query and maximising 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. Letās consider the above image as example and we want maximum xor with ā110ā in range [1,2] (note the zero indexing):
About inserting a number x which occurs at position y in array, we express x in binary and then traverse the trie and at each step push the value y at each vector of node that we pass through.
So, a total of log(x) times, weāll push y in different vectors. Therefore, total memory used wonāt exceed M*log(MAX). These vectors will always be sorted as we insert in increasing order of y.
About deleting last k elements, we can do it in O(h * k)(h=height of trie = log MAX). Point worth noting is that sum of k over all deletion queries canāt exceed M. So, we can do deletions in O(h * k). While deleting one element from end, we just go traverse over the trie along the path of element being deleted and pop from the end of the vector(ie. pop the index of element) at each node.
Now, about the type4 query, we need kāth smallest element in range L to R.
Again, letās solve for L=1, R=N.
I start from the root, and at each step I know, that if I go towards left, Iāll encounter say K1 leaves(numbers) and at right side Iāll encounter K2 leaves(numbers) and considering that all numbers on left side are smaller than those at right side, I can easily make a decision whether I want to go to left side or right side(ie. whether this bit of my answer will be set or not, we already have calculate previous bits of our answer).
Similarily to the way we handle xor range queries, we can do for a range query in kāth order statistics. We can count number of indexes in range [L,R] in a vector using lower_bound, upper_bound.