By too_shy_to_ask_with_real, history, 12 months ago,

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.

 » 12 months ago, # |   +3 The problem is very similar to this.
 » 12 months ago, # |   0 Operation 1 equivalent is 242E - XOR на отрезке. For operations 2 and 3 we can use lazy propagation.
 » 12 months ago, # |   0 It is not over yet.
•  » » 12 months ago, # ^ |   0 I think they must have repeated the same problem. This looks 3 hr contest and I asked it yesterday.
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 Hint 1Notice the number of nodes were <= 16. Hint 2Instead of making choice on deleting the edge, can you make choice on keeping the nodes? As deleting an edge until completely isolating the node won't have any impact on result. Result only gets affected when some node is removed. Solution ApproachFind all connected component for each of 2^A graphs (subsets of nodes) and calculate results.