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

**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:

##### Subtask 1

Iterating the softwares for each query suffices.

**Time Complexity:**

##### 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 element has value if it is a gatcha game, and 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 solution, which we can optimize to by walking the segment trees in parallel.

**Time Complexity:**

##### Subtask 3

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

**Time Complexity:**

##### 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 element has value if it is a gatcha game, and otherwise. Do the same for the auxiliary 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:**

## Comments