Range bit flips in a range of numbers ?
Разница между en1 и en2, 6 символ(ов) изменены
[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())?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский mohamedeltair 2018-03-28 10:07:37 38 Tiny change: ')|rand())?' -> ')|rand())?\n\nNote: rand() here is the C++ rand.'
en3 Английский mohamedeltair 2018-03-28 06:41:00 6
en2 Английский mohamedeltair 2018-03-28 06:40:11 6
en1 Английский mohamedeltair 2018-03-28 06:31:17 1756 Initial revision (published)