Game with Stones
Contest: Technocup 2022 - Elimination Round 2
Difficulty rating: 2300
Tags: binary search, data structures, games, greedy

Bob decided to take a break from calculus homework and designed a game for himself.

The game is played on a sequence of piles of stones, which can be described with a sequence of integers $$$s_1, \ldots, s_k$$$, where $$$s_i$$$ is the number of stones in the $$$i$$$-th pile. On each turn, Bob picks a pair of non-empty adjacent piles $$$i$$$ and $$$i+1$$$ and takes one stone from each. If a pile becomes empty, its adjacent piles do not become adjacent. The game ends when Bob can't make turns anymore. Bob considers himself a winner if at the end all piles are empty.

We consider a sequence of piles winning if Bob can start with it and win with some sequence of moves.

You are given a sequence $$$a_1, \ldots, a_n$$$, count the number of subsegments of $$$a$$$ that describe a winning sequence of piles. In other words find the number of segments $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$), such that the sequence $$$a_l, a_{l+1}, \ldots, a_r$$$ is winning.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
Print a single integer for each test case — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Bob can't win on subsegments of length $$$1$$$, as there is no pair of adjacent piles in an array of length $$$1$$$.

In the second test case, every subsegment is not winning.

In the fourth test case, the subsegment $$$[1, 4]$$$ is winning, because Bob can make moves with pairs of adjacent piles: $$$(2, 3)$$$, $$$(1, 2)$$$, $$$(3, 4)$$$. Another winning subsegment is $$$[2, 3]$$$.

Example input:
6
2
2 2
3
1 2 3
4
1 1 1 1
4
1 2 2 1
4
1 2 1 2
8
1 2 1 2 1 2 1 2

Example output:
1
0
4
2
1
3

Editorial:
This game has greedy strategy: look at first pile, all its stones have to be matched with stones from next pile, because it is its only adjacent pile. If pile is non-empty and there are no next pile, or next pile is smaller than current, Bob loses. Otherwise, Bob makes current pile empty, and remove corresponding number of stones from next pile. Now Bob plays the same game as if had one pile less, we can remove first pile without changing game. Bob wins if at the moment he reduced game to one pile it's already empty.
Now let's iteratively define array $$$c$$$, where $$$c_i$$$ — number of stones left in the $$$i$$$-th after removing $$$1, \ldots, i - 1$$$ piles, according to greedy strategy. Let $$$c_0 = 0$$$, then $$$c_i = a_i - c_{i - 1}$$$.
If array contains only positive numbers, then it means that Bob is able to remove piles all the way over. Otherwise, let $$$t$$$ be the first moment with $$$c_t < 0$$$, this means that Bob was able to remove piles until he meet $$$t$$$-th pile and $$$c_{t-1} > a_t$$$ happened, so Bob loses. To check that last pile is empty, we need to check if $$$c_n = 0$$$.
So we have criteria of winning subsequence: $$$c_i \geq 0$$$ for all $$$i$$$, $$$c_n = 0$$$.
Let's expand recursive notation of $$$c_i$$$: $$$c_i = a_i - a_{i - 1} + a_{i - 2} -\ldots + (-1)^{i-1} \cdot a_1$$$.
We will solve problem separately for different $$$l$$$ — left bound of subsegment. Let's define sequence $$$a^l := a_l, a_{l+1} \ldots a_n$$$, $$$a_i^l = a_{l + i - 1}$$$. It has similar array $$$c^l$$$. We will find first position of negative number in $$$c^l$$$ —$$$t$$$ ($$$c_t^l < 0$$$). And then count how may zeros are on prefix [$$$1$$$, $$$t-1$$$]. This will give us number of winning subsegemtns with form $$$[l, r]$$$, sum over all $$$l$$$ will give us answer for the problem.
Note, that $$$c_i^l = a_i^l - a_{i - 1}^l + \ldots + (-1)^{i-1} \cdot a_1^l = a_{l+i-1} - a_{l+i-2} + \ldots + (-1)^{i-1} \cdot a_{l} = c_{l+i-1} + (-1)^{i-1} \cdot c_{l - 1}$$$.
Note, that $$$c_i^l < 0$$$ if and only if $$$c_{l + i - 1} < (-1)^{i - 1} \cdot c_{l - 1}$$$. Let's divide problem by parity of indexes. Now to find first position of negative number in $$$c^l$$$ we should find first position of "number less than x" on suffix of $$$c$$$. This can be done many ways, for example, by descending through segment tree (segment tree for each parity).
Note, that $$$c_i^l = 0$$$, if and only if $$$c_{l + i - 1} = (-1)^{i - 1} \cdot c_{l - 1}$$$. Same division of problem by parity. Now to count number of zeros on subsegment of $$$c_l$$$ we should count number of "equals to x" on subsegment of $$$c$$$. This can be done by storing all positions of each $$$c_i$$$ in some container (one for each parity) and binnary search.
Overall complexity of the solution : $$$\mathcal{O}(n \cdot log(n))$$$