How to make Difference array(or something similar) for AND operation

Initially, we are given an Array of N non-negative integers. After that, we have to perform Q queries and finally print the modified Array.
Each query looks like this: L R X, here we have to change the array elements from L to R (Both inclusive) to AND of X and previous element. That means Ai changes to (X & Ai).

Constraints

  • 1 ≤ N ≤ 2*10^5

  • 0 ≤ Ai ≤ 10^9

  • 1 ≤ Q ≤ 2*10^5

  • 1 ≤ L, RN

  • 0 ≤ X ≤ 10^9

Note: If the operation were SUM instead of AND then, it could be easily solved by using the Difference array, but I am unable to think something similar for AND operation. Help will be really appreciated :slight_smile:

1 Like

It can be easily solvable with square root decomposition . Just maintain an extra array b of size sqrt(n)+1 , where b(i) stores the AND value to be done over all the elements inside the block i.

Thanks ,

3 Likes

Link to the problem?

btw can we also use segment tree here ?

Yeah ! We can apply the same idea for updation using segment tree with lazy propogation :slight_smile:

1 Like

This will actually give TLE.
An O(n) solution has been discussed here (Comment of antontrygubO_o)
https://codeforces.com/blog/entry/71445

You can actually solve this using diff array.
Keep diff array for each bit and decrement them in range l,r if current bit it 0.
And you can easily solve this problem.