Auto comment: topic has been updated by omeganot (previous revision, new revision, compare).

Thank you so much for writing this! Your explanations are not overly wordy at all. I appreciate the extra detail.

holy moly omeganot

I will share the slightly different solution for problem I (Advanced Division) that AlesL0 and I came up with.

Let's consider a prefix of the query range of length $$$K$$$ with distinct elements, where the maximum element is $$$M$$$. The answer for that prefix is therefore $$$M - K$$$. If I extend this prefix by one position by adding element $$$i$$$, three things can happen:

• If I find a duplicate element, I'm done because I can't extend any further.
• If $$$a_i \lt M$$$, the answer decreases by $$$1$$$.
• If $$$a_i \gt M$$$, the answer increases and becomes $$$a_i - (K + 1)$$$. This happens when the minimum of the prefix changes.

So I'm interested in the local minima of the answer before the maximum of the prefix changes.

To do this, I can consider the tree in which each element is the child of the next greater element. The weight of the edge is the value of the answer (without considering the query offset) in the local minimum before going to the parent.

By performing binary lifting on this tree, it is possible to answer queries online.

To check for duplicates, it is enough, for example, to have a sparse table that tells the minimum index of the next equal element for a range.

Submission code here

As a tester, here is a different solution to stones:

Note that we can always some operations to do the following $$$2$$$ moves.

1) add ($$$-1$$$, $$$-1$$$) to $$$i$$$ and ($$$+1$$$, $$$+1$$$) to $$$j$$$, $$$i \neq j$$$.

2) If you have $$$\ge n - 2$$$ white and $$$\ge n - 2$$$ black stones at at least one other stone of any color in a pile we can add $$$(-(n - 2), -(n - 2))$$$ to this pile.

It makes sense that we would want to stack as many pairs of opposite colored stones in one pile and then use the second move as much as we can.

Let $$$c$$$ be $$$\sum_{i=1}^n \text{min}(b[i], w[i])$$$. We can increase $$$c$$$ further by doing a move we subtract each pile of black or each pile of white by $$$1$$$ as long as they are all positive.

Note that at this point each pile has either a positive number of black or white stones and then we can pretend we set all the $$$c$$$ pairs on the side.

However, it may be optimal do more type $$$1$$$ or type $$$2$$$ operations to increase $$$c$$$ before we subtract $$$n - 2$$$ as many times as possible.

When we increase the entire array in a type $$$1$$$ operation, $$$c$$$ increases by the amount of piles with positive black stones minus $$$1$$$ and then each of these piles decrease in size by $$$1$$$ (and similar logic for type $$$2$$$ operation but with white stones).

Its never optimal to do both extra type $$$1$$$ and type $$$2$$$ operations because at most you can get $$$n - 2$$$ extra pairs and they "cancel" out.

We can simulate this in $$$O(n \cdot (w + b))$$$.

However, we can notice that we don't need to simulate it directly and it only depends on the number of positive elements in the side we are doing extra operations to subtract from and the total number of black and white stones.

We can sort the array to find out when the number of positive numbers changes and maintain the sums as we do more extra operations.

We can use this to speed up the simulation to $$$O(n \log n + w + b)$$$

To speed this up further we can consider every interval where the number of positive piles is the same. Call this $$$k$$$. At every step the sum of the array will change by $$$n - 2 \cdot k$$$ and the number of pairs increases by $$$k - 1$$$.

Because the pairs are taken mod $$$n - 2$$$ we can't just check the first and last values of the interval. However, it is enough to check the first and last $$$\frac{2n}{k}$$$ in order to find the global minimum (on this segment). This is fast enough because $$$\sum_{i=1}^n \frac{n}{i} \approx n \log n$$$

Since there are only $$$n$$$ different possible values of $$$k$$$ the total time complexity is $$$O(n \log n)$$$.

Code: https://pastebin.com/DYLEYN37