CF1694B Paranoid String

我们称长度为 $m$ 的二进制字符串 $T$（下标从 $1$ 到 $m$）为“paranoid”，如果可以通过以下两种操作共 $m-1$ 次（顺序任意）将其变为长度为 $1$ 的字符串： - 选择 $T$ 的任意一个等于 $01$ 的子串，并将其替换为 $1$。 - 选择 $T$ 的任意一个等于 $10$ 的子串，并将其替换为 $0$。 例如，如果 $T=001$，我们可以选择子串 $[T_2T_3]$ 并执行第一种操作，得到 $T=01$。 给定一个长度为 $n$ 的二进制字符串 $S$（下标从 $1$ 到 $n$）。请你求出有多少对整数 $(l, r)$ 满足 $1 \le l \le r \le n$，使得 $S[l \ldots r]$（即 $S$ 的第 $l$ 位到第 $r$ 位的子串）是一个“paranoid”字符串。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $S$ 的长度。 第二行包含一个长度为 $n$ 的二进制字符串 $S$，即 $S_1S_2\ldots S_n$（$S_i=0$ 或 $S_i=1$，$1 \le i \le n$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示有多少对整数 $(l, r)$ 满足 $1 \le l \le r \le n$，使得 $S[l \ldots r]$ 是一个“paranoid”字符串。

在第一个样例中，$S$ 已经是长度为 $1$ 的字符串，不需要任何操作。 在第二个样例中，$S$ 的所有子串都是“paranoid”。对于整个字符串，只需执行一次第一种操作即可。 在第三个样例中，除了 $[S_2S_3]$（因为无法对其进行任何操作）和 $[S_1S_2S_3]$（整个字符串）之外，所有子串都是“paranoid”。 由 ChatGPT 4.1 翻译