Codeforces Round #755 (Div. 2) Game with Stones Solution (Java/C++)

Solution:

First of all, we noticed that for the first pile of stones, it must be operated with the second pile of stones. And when the first pile of stones is taken to empty, the second pile of stones must be operated with the third pile of stones in the same way. By analogy, we find that the operations must be performed sequentially from left to right.
Therefore, we maintain an array after_left to record the number of stones left after the pile of stones on the left was taken (it can be a negative number). Obviously, after_left[i]=a[i]-after_left[i-1]. Take a=[1,2,5,1,1] as an example, after_left=[1,1,4,-3,4].

Now we consider the case of intercepting a sub-array. Based on the above conclusions, we still consider from left to right. Obviously, at this time we need to increase after_left[l] by a[l]-after_left[l] to offset the impact of the pile of stones on its left.
When after_left[l] increases a[l]-after_left[l], after_left[l+1] decreases a[l]-after_left[l]. Decreasing after_left[l+1] will cause after_left[l+2] to increase by a[l]-after_left[l]. And so on.

So this idea is very natural. We consider how to judge whether the sub-array from l to r can win. We mark diff=a[l]-after_left[l]. So it is obvious that if this sub-array can win, there must be:$$\begin{cases}
\text{after_left[i]}+\text{diff}\geq 0, & i-l \equiv 0 (mod 2)\\
\text{after_left[i]}-\text{diff}\geq 0, & i-l \equiv 1 (mod 2)\\
\text{after_left[r]}\pm \text{diff}= 0\\
\end{cases}$$Because after the change, each pile of stones in the sub-array must not appear negative. At the same time, after the change, the remainder of the last pile of stones must be zero.

So the solution is very natural. According to the parity of the indexes, we use the segment tree to maintain the minimum value for interval respectively.
So we can enumerate the values of l from small to large. For each l, we find a maximum r through binary search, so that the minimum value after adjustment is greater than or equal to 0.
At the same time, we use two Maps to record the mapping between the value of after_left and the indexes according to the parity of the index.

So we enumerate l in turn, and use the minimum value of the interval maintained by the segment tree to find the maximum r through binary search.
Then in the range from l to r, get all the indexes of $\pm \text{diff}$ according to the parity.
Finally, we use l and r to filter out all the indexes in the range through binary search.

Code:

Java

C++