Initially, we are given an Array of *N* non-negative integers. After that, we have to perform *Q* queries on it 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^50 ≤

*Ai*≤ 10^91 ≤

*Q*≤ 2*10^51 ≤

*L, R*≤*N*0 ≤

*X*≤ 10^9

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

Can you post the problem source so we know it’s not from an ongoing contest?

I don't have a link. This problem is not from any contest. It was asked to me in the campus placement test of Walmart.

I guess you can solve this for single bit then do the same over the rest of the bits .

For single bit process queries in off-line manner.

You will specific segments ranges (l1, r1); (l2,r2)......(lm,rm) over which the i bit is set 1 where 0 <= lk, rk<= n-1.

You can update as ans[j] += val[j]&(1<<i); for all j that is covered in the above segment.

ok

it can be solved by segment tree for every bit. If this bit 1 in X it won't change count of this bits, if it's 0 — it will delete all such bits from l to r, you need say then $$$tree[bit][i] = 0, i \in [l, r]$$$ so, to take sum you can sum $$$2^{bit} \cdot tree[bit][i], i \in [l, r]$$$

segment tree

alternatively you can build an OR segement tree $$$s$$$ (filled with 0b111111...) and make the query $$$[l, r]$$$ ~$$$X$$$ instead. At the end the result is then $$$A_i$$$ AND ~$$$s_i$$$. (~ means bitwise not)

I think the seg tree isn't needed as we only have to print the array in the end. We just have to find for some $$$i$$$ and $$$bit$$$ if $$$a[i]$$$ was covered by some segment with $$$x$$$ which has $$$bit$$$ off. But for a set of segments we can count which elements are covered by at least one of them, in linear time.

Thanks, Everyone. I got the logic/idea.