too_shy_to_ask_with_real's blog

[Help] Encuntered this problem on Range Query on bit array in recent contest
By too_shy_to_ask_with_real, history, 12 months ago, In English

Problem source: (Codedrift June, Interviewbit)

Given an integer array X with size A. Initially all the elements of this array are 0. Given another integer array Y with the same size A, all the elements here are also 0. You have to handle three types of queries:

1 L R — Flip all elements from 0 to 1 and 1 to 0 in range L to R (inclusive) in array X

2 P — For every element i in [1, A], do: Y[i] += X[i] * P

3 J — Find Y[j]

A <= 10^5 and Q <= 10^5

Would really be great if you could provide approach or hint. Contest is over. Here's the link to contest.

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The problem is very similar to this.

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

Operation 1 equivalent is 242E - XOR на отрезке. For operations 2 and 3 we can use lazy propagation.

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

It is not over yet.

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

Maybe off topic but how to solve the graph problem in this contest in which we have to divide the graph into subgraphs and maximise the result.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    Solution Approach
    → Reply