Subtask 1

The key observation is that after fixing the last rocket used to complete the race, the previous rockets can be determined greedily in decreasing order of ~a_i - b_i~. For this subtask, it is sufficient to explicitly maintain an array of the rockets sorted in decreasing order of ~a_i - b_i~, binary searching on the prefix sums of this array for each of the ~N~ candidate last rockets. One detail to note is that the prefix sum array may not be in increasing order because ~a_i - b_i~ could be negative, so binary search may fail to give the correct answer. To fix this, we may simply set ~b_i = \min(a_i, b_i)~ for every single rocket. This is valid because the only case we would ever use a rocket where ~a_i < b_i~ is as the last rocket, in which case the value of ~b_i~ is of no significance.

Time Complexity: ~\mathcal{O}(QN \log N)~

Subtask 2

We can no longer loop through every possible last rocket. Instead, let's binary search on the minimum number of rockets that can be used to complete the race. Once again, we store the rockets in decreasing order of ~a_i - b_i~. If we consider using ~k~ rockets, the maximum forward distance can be calculated by considering the two following cases:

1. The last rocket is some rocket in the range ~[1, k]~. The maximum forward distance is then ~\sum_{i=1}^k (a_i - b_i) + \max_{i=1}^k b_i~.
2. The last rocket is some rocket in the range ~[k+1, N]~. The maximum forward distance is then ~\sum_{i=1}^{k-1} (a_i - b_i) + \max_{i=k+1}^N a_i~.

All the required values can be precomputed in ~\mathcal{O}(N)~ and accessed in ~\mathcal{O}(1)~, leaving us with ~\mathcal{O}(\log N)~ time per query.

Time Complexity: ~\mathcal{O}((N+Q) \log N)~

Subtask 3

We must now consider how to maintain the array stored in the previous subtask as updates are performed. There are many possible methods, but the simplest of them is to use a segment tree indexed by coordinate-compressed ~a_i - b_i~. If we store the number of rockets, sum of ~a_i - b_i~, maximum ~a_i~, and maximum ~b_i~ in each node of the segment tree, we can obtain the required values for each binary search iteration by walking down the segment tree. This allows us to perform updates in ~\mathcal{O}(\log N)~ and answer queries in ~\mathcal{O}(\log^2 N)~, sufficient for full marks.

Time Complexity: ~\mathcal{O}(N \log N + Q \log^2 N)~

Remark: It is also possible to answer queries with a single walk down the segment tree obtaining ~\mathcal{O}((N+Q) \log N)~ time complexity, although this is not necessary at all given the lenient constraints on ~N~ and ~Q~.