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 kth smallest integer (kth order statistic).
1 ≤ M ≤ 5 * 105
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.