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)~