codeingerman's blog

By codeingerman, 4 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks, Everyone. I got the logic/idea.