## 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

Iterating the softwares for each query suffices.

Time Complexity:

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 th element has value if it is a gatcha game, and otherwise. Do the same for the one corresponding the 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 an subinterval is all of 1 type, we can query the third segment tree instead.

This gives us an solution, which we can optimize to by walking the segment trees in parallel.

Time Complexity:

Time Complexity:

Maintain two more auxilliary segment trees: one for gatcha games, and one for math software. In the auxilliary segment tree corresponding to gatcha games, the th element have value if it is a gatcha game, and otherwise. Do the same for the auxilliary segment tree corresponding to math software.

To deal with a range update of 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 solution, which we can again optimize by walking the segment trees in parallel.

Time Complexity: