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.

The problem is very similar to this.

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

It is not over yet.

I think they must have repeated the same problem. This looks 3 hr contest and I asked it yesterday.

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.

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.