CF1750H BinaryStringForces

给定一个长度为 $n$ 的二进制字符串 $s$。我们将“极大子串”定义为：无法在保持所有元素相同的情况下继续向两边扩展的子串。例如，在字符串 $11000111$ 中，有三个极大子串：$11$、$000$ 和 $111$。 每次操作，你可以选择两个相邻的极大子串。由于它们是极大且相邻的，显然它们的元素值必然不同。设 $a$ 为连续 $1$ 的长度，$b$ 为连续 $0$ 的长度。然后进行如下操作： - 如果 $a \ge b$，则将这 $b$ 个 $0$ 替换为 $b$ 个 $1$。 - 如果 $a < b$，则将这 $a$ 个 $1$ 替换为 $a$ 个 $0$。 例如，对于 $1110000$，可以变为 $0000000$；对于 $0011$，可以变为 $1111$。我们称一个字符串是“好”的，如果它可以通过上述操作任意次（可以为零次）变为 $1111\ldots1111$。 请你统计，对于 $s$ 的所有 $\frac{n(n+1)}{2}$ 个非空子串中，有多少个是“好”的。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来每组测试数据包含两行： 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示字符串 $s$ 的长度。 第二行包含一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示“好”子串的数量。

我们将下标从 $l$ 到 $r$ 的子串记作 $[l, r]$。 对于第一个测试用例，所有“好”子串为： - $[1,1]$， - $[1,2]$， - $[3,6]$， - $[4,5]$， - $[4,6]$， - $[5,5]$， - $[5,6]$， - $[6,6]$。 第二个测试用例中，除了 $[2,2]$ 外，所有子串都是“好”的。 第三个测试用例中，所有子串都是“好”的。 由 ChatGPT 4.1 翻译