GEHA1803 - Editorial

PROBLEM LINKS:

Practice

Contest

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: Setter's solution Tester's solution Feel free to comment if you have any doubt .
//