### codeingerman's blog

By codeingerman, 12 months ago,

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^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 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.

• 0

 » 12 months ago, # |   +10 Can you post the problem source so we know it’s not from an ongoing contest?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +8 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<
 » 12 months ago, # |   +15 okit 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
•  » » 12 months ago, # ^ |   0 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)
•  » » 12 months ago, # ^ |   +17 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.
 » 12 months ago, # | ← Rev. 2 →   0 Thanks, Everyone. I got the logic/idea.