For the first subtask, brute-force all possible subarrays for each query.

Time Complexity: ~\mathcal O(QN^2)~

For the second subtask, consider each element. Using two stacks, we can determine the index of the rightmost element to the left of it which is strictly less than it, and the leftmost element to the right of it which is strictly less than it. Then for each query, we only need to loop through each element instead of all subarrays.

Time Complexity: ~\mathcal O(QN)~

For the third subtask, note that the answer to each query is either the suffering of the longest subarray which contains only the greater value, or it is the suffering of the entire subarray. The first value can be computed using a segment tree. The other value is easy to compute.

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

There are two solutions to the fourth subtask. One simply extends the solution to the third subtask. The other, which we will discuss, sheds light on the full solution.

Let ~par[i][0]~ be the rightmost element to the left of ~i~ which is strictly less than ~v_i~, and ~par[i][1]~ be the leftmost element to the right of ~i~ which is strictly less than ~v_i~. As mentioned in the solution to subtask 2, these values can be computed in ~\mathcal O(N)~. Also, remember that for a minimum element at index ~i~, we only need to consider its subarray from ~\max(l, par[i][0]+1)~ to ~\min(r, par[i][1]-1)~.

Consider a subarray contained within an array. There are three cases: the subarray contains the leftmost element, it contains the rightmost element, or it contains neither. For the first case, note that we only need to consider when ~l~, ~par[l][0]~, ~par[par[l][0]][0]~, and so on are the indices of the minimum elements. Let ~K~ be the number of distinct values. Since ~K~ is small, this can be done quickly. The second case is handled similarly.

For the third case, we only need to consider when ~l \le par[i][0]+1~ and ~par[i][1]-1 \le r~. We can use a segment tree and handle the queries offline.

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

Some users have noticed that the subtasks were taken from IOI '18 F. Indeed, the full solution bears some similarities.

For the final subtask, we speed up the solution described for subtask 4. Specifically, the first two cases must be sped up. Note that the ~par~ values defined implicitly build two trees. Also, when stopping at a certain index ~j~ (which was some ~par[par[\dots][\dots]][0]~) in the first case, then the suffering obtained is ~v_j\cdot (prefix\_sum[par[j][0]-1]-prefix\_sum[l-1]) = m_j x + b_j~, where ~x=prefix\_sum[l-1], m_j = -v_j, b_j = v_j\cdot prefix\_sum[par[j][0]-1]~.

So the first two cases become a convex hull problem on the path of two trees. This can be done by performing heavy-light decomposition and building a segment tree of convex hulls. Sorting the queries based on left/right endpoint (depending on which case) can speed up the ~\mathcal O(\log^3 N)~ per query to ~\mathcal O(\log^2 N)~ per query (during testing, there was very little change in performance from this optimization).

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