[The problem](https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/big-number-array-043361b7/)↵
↵
There are two types of queries in the problem:↵
↵
1. flip from the Lth bit to the Rth bit inclusive in the elements from index x to index y inclusive↵
2. answer that question: is the xth number equal to the yth number ?↵
↵
The elements are all initially zeros. N and Q (numbers of elements and queries) are up to 1e5. And 0 <= l <= r <= 1e9.↵
↵
An intuitive idea (if the number of bits was small) is:↵
↵
for the 1st query type: xor elements in the range [x,y] with (2^(r+1)-1 xor 2^(l)-1) (can be done easily using range update structures)↵
for the 2nd query type: just check if the xth elements is equal to the yth elements using a point query↵
↵
But the number of bits is very large, I noticed from people's solutions that they hashed 2^x for all x that appeared in the first query type (l and r) to represent them in smaller numbers. So any mask which was originally (2^(r+1)-1 xor 2^(l)-1) maps to a another mask which is (hash(r+1) xor hash(l)). and the original combination of 1e9+1 bits for any element will map to a combination of smaller number of bits.↵
↵
This type of solution has two sides in the second query type:↵
↵
1. if the answer is Yes, it is guaranteed that this solution will output Yes.↵
2. if the answer is No, it may happen that that two different combination of 1e9+1 bits map to the same combination in the smaller number of bits, and hence the solution will output Yes.↵
↵
What is the probability that the problem in the second side happens if (for example) the hash for any 2^x was a long long in the form of (rand()<<32)|rand())?
↵
There are two types of queries in the problem:↵
↵
1. flip from the Lth bit to the Rth bit inclusive in the elements from index x to index y inclusive↵
2. answer that question: is the xth number equal to the yth number ?↵
↵
The elements are all initially zeros. N and Q (numbers of elements and queries) are up to 1e5. And 0 <= l <= r <= 1e9.↵
↵
An intuitive idea (if the number of bits was small) is:↵
↵
for the 1st query type: xor elements in the range [x,y] with (2^(r+1)-1 xor 2^(l)-1) (can be done easily using range update structures)↵
for the 2nd query type: just check if the xth elements is equal to the yth elements using a point query↵
↵
But the number of bits is very large, I noticed from people's solutions that they hashed 2^x for all x that appeared in the first query type (l and r) to represent them in smaller numbers. So any mask which was originally (2^(r+1)-1 xor 2^(l)-1) maps to a another mask which is (hash(r+1) xor hash(l)). and the original combination of 1e9+1 bits for any element will map to a combination of smaller number of bits.↵
↵
This type of solution has two sides in the second query type:↵
↵
1. if the answer is Yes, it is guaranteed that this solution will output Yes.↵
2. if the answer is No, it may happen that that two different combination of 1e9+1 bits map to the same combination in the smaller number of bits, and hence the solution will output Yes.↵
↵
What is the probability that the problem in the second side happens if (for example) the hash for any 2^x was a long long in the form of (rand()<<32)|rand())?
