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, R ≤ N
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
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.
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.