PROBLEM LINKS:
DIFFICULTY:
Medium
PREREQUISITES:
Trie and Persistent Data Structures.
PROBLEM:
Given an array of N integers and Q queries where each query contains four integers l r x y find the number of elements in the range l to r whose bitwise xor with x results in a number greater than or equal to y .
QUICK EXPLANATION
Consider a function f(i,x,y) which returns the number of elements in the range 1 to i whose bitwise xor with x is greater than or equal to y . If we can calculate f(i,x,y) for all i then the answer for each query will be f(r,x,y) - f(l-1,x,y). We will use persistent trie to calculate f(i,x,y) efficiently.
EXPLANATION
If you don’t know about persistent data I would recommend reading about it from here before proceeding any further . For the rest of the editorial I would be assuming you know how to create persistent data structures .
Let us denote the the trie formed by elements from 1 to i as root[i] . root[i] can be calculated from root[i-1] in O(log(n)) using the concept of persistent data structures .
Our trie block will be like this:
struct Trie
{
Trie *child[2];
int cnt;
}
child[0] and child[1] are trie pointers which point to respective subtree of trie depending upon whether corresponding bit is set or unset . cnt stores the number of elements in the subtree of the current trie node . Our problem now reduces to finding the number of elements whose bitwise xor with x is greater than or equal to y in a given trie . Consider the binary representation of x and y , there will be four cases:
- Current bit of x is 1 and Current bit of y is also 1 , then all the numbers whose Current bit is 1 when taken xor with with x will result in a number lesser than y and for all the numbers whose Current bit is 0 may or may not result in a number greater than or equal to y when taken xor with x so we will move to the subtree of which contains 0 at the Current bit i.e , child[0] .
- Current bit of x is 0 and Current bit of y is 1 , then all the numbers whose Current bit is 0 when taken xor with x will result in a number lesser than y and for all the numbers whose Current bit is 1 may or may not result in a number greater than or equal to y when taken xor with x so we will move to the subtree of which contains 1 at the Current bit i.e , child[1] .
- Current bit of x is 1 and Current bit of y is 0 , then all the numbers whose Current bit is 0 when taken xor with with x will result in a number greater than y so we will directly add the cnt of that subtree in our answer and for all the numbers whose Current bit is 1 may or may not result in a number greater than or equal to y when taken xor with x so we will move to the subtree of which contains 1 at the Current bit i.e , child[1] .
- Current bit of x is 0 and Current bit of y is also 0 , then all the numbers whose Current bit is 1 when taken xor with x will result in a number greater than y so we will directly add the cnt of that subtree in our answer and for all the numbers whose Current bit is 0 may or may not result in a number greater than or equal to y when taken xor with x so we will move to the subtree of which contains 0 at the Current bit i.e , child[0] .
Current Bit will initially be equal to 32 (depending upon the implementation of your trie) and each time we move to a subtree we will decrement the value of Current Bit by 1 . We will continue this process until the value of Current Bit is greater than or equal to 0 .
Time Complexity
Time complexity of the above solution is O(Nlog(n)) pre-processing and O(log(n)) per query . Hence total time complexity will be O(Nlog(n)+Qlog(n))
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to comment if you have any doubt .