CF1584E Game with Stones

Bob 决定暂时放下微积分作业，给自己设计了一个游戏。 这个游戏在一组石子堆上进行，可以用一组整数 $s_1, \ldots, s_k$ 来描述，其中 $s_i$ 表示第 $i$ 堆石子的数量。每一回合，Bob 选择一对非空且相邻的石子堆 $i$ 和 $i+1$，并从每一堆中各取出一颗石子。如果某一堆变为空堆，则它的相邻堆不会因此变为相邻。游戏在 Bob 无法再进行操作时结束。如果最后所有石子堆都为空，Bob 认为自己获胜。 我们称一组石子堆为“获胜序列”，如果 Bob 能以某种操作顺序使得最终所有石子堆都为空。 现在给定一个序列 $a_1, \ldots, a_n$，请你统计有多少个子区间 $[l, r]$（$1 \leq l \leq r \leq n$），使得序列 $a_l, a_{l+1}, \ldots, a_r$ 是一个获胜序列。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 3 \cdot 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示满足条件的子区间数量。

在第一个测试用例中，长度为 $1$ 的子区间都无法获胜，因为长度为 $1$ 的数组中没有一对相邻的石子堆。 在第二个测试用例中，每个子区间都不是获胜序列。 在第四个测试用例中，子区间 $[1, 4]$ 是获胜序列，因为 Bob 可以依次选择相邻的石子堆对 $(2, 3)$、$(1, 2)$、$(3, 4)$ 进行操作。另一个获胜的子区间是 $[2, 3]$。 由 ChatGPT 4.1 翻译