shivam_360's blog

Can someone suggest some possible approach for this problem..
By shivam_360, history, 18 months ago, In English

You are given an array a of length n and q queries... A query is in the form [l,r,x].. First, you need to replace each a[i] with a[i]^x for each i from l to r and then answer for the query will be bitwise OR of all a[i] for each i from l to r... here the changes of each query will permanently reflect in the array...and every time we process on the updated array... constraints: N and q <=10^5 A[i] and x <=10^9 L<=r<=N

suggest some of the possible way to approach this problem and some of intuition for in general solving this type of range update questions.... i think...some kind of segment tree or BIT solution must be there...

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Range updates and range queries, you'd probably need a segment tree with lazy propagation. I was able to solve the problem with one, but the solution is not very trivial and I don't really want to explain it here. I don't think it's possible to solve the problem without lazy prop segment trees, but I may be wrong.

Segment trees with lazy propagation are quite an advanced data structure, and it just doesn't really make any sense for a 1300-rated user to learn about them. You'd be better off just solving a lot of problems at your level instead of studying advanced data structures. But if you really insist, I can give an explanation of this problem. But you need to be familiar with lazy prop segment trees already (and properly understand how and why they work), I'm not going to be teaching you that.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, Giving just idea and intuition will be okay...

    → Reply
»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

link to the problem?

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can try do something like this: make 30 arrays, ith position in jth array will be 0/1 depending on jth bit in ith number in intial array, and then make 30 segtrees on each array, and in nodes of trees will be number of ones and zeros. When we have type 1 query, we iterate all bits in x, and if ith bit is 1, we need to invert bits in ith segtree in range [l; r], you can make it with lazy segtree and swaping number of zeros and ones in each node that the segment contains. When we have type 2 query, firstly ans = 0, then we iterate i = 0...30, and if value of ones in segment [l; r] in array responsible for bits on ith position is at least 1, ith bit in ans will be 1, else 0. This work in O(logN * logA) for each query which should get AC. Also, can you provide link to this problem?

→ Reply