[Help] Encuntered this problem on Range Query on bit array in recent contest

Revision en1, by too_shy_to_ask_with_real, 2022-06-11 22:18:03

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.

Tags bitarray, range update, #bitflip

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English too_shy_to_ask_with_real 2022-06-11 22:18:03 732 Initial revision (published)