There are two types of queries in the problem:
- flip from the Lth bit to the Rth bit inclusive in the elements from index x to index y inclusive
- 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:
- if the answer is Yes, it is guaranteed that this solution will output Yes.
- 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())?
