Editorial for DMOPC '20 Contest 1 P6 - Victor Identifies Software


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

Subtask 1

Iterating the softwares for each query suffices.

Time Complexity: \mathcal O(NQ)

Subtask 2

Consider a simpler problem where we do not change the type of software.

Create 2 segment trees: one for gatcha games, and one for math software. In the segment tree corresponding to gatcha games, the i^\text{th} element has value a_i if it is a gatcha game, and -\infty otherwise. Do the same for the one corresponding to math software.

The problem can thus be reduced to the classic maximum subarray sum problem.

Reintroducing updates, we can handle them by constructing a third segment tree to solve the maximum subarray sum problem over the whole array. If a subinterval is all of 1 type, we can query the third segment tree instead.

This gives us an \mathcal O(N\log^2 N) solution, which we can optimize to \mathcal O(N\log N) by walking the segment trees in parallel.

Time Complexity: \mathcal O(N\log N)

Subtask 3

Simply add point updates to the solution outlined in subtask 2.

Time Complexity: \mathcal O(N\log N)

Subtask 4

Maintain two more auxiliary segment trees: one for gatcha games, and one for math software. In the auxiliary segment tree corresponding to gatcha games, the i^\text{th} element has value 1 if it is a gatcha game, and -\infty otherwise. Do the same for the auxiliary segment tree corresponding to math software.

To deal with a range update of a_i values, the maximum prefix, suffix, and subinterval sums of gatcha games correspond to the longest prefix, suffix, and subinterval multiplied by the value, respectively, of consecutive gatcha games if the new value is positive. If the new value is negative, these values correspond to the new value itself. The same is true for math software. We can easily query for these values from the newly introduced segment trees.

This gives us an \mathcal O(N\log^2 N) solution, which we can again optimize by walking the segment trees in parallel.

Time Complexity: \mathcal O(N\log N)


Comments

There are no comments at the moment.