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.

sorry to necropost, can you please tell me the time complexity for this?

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.