CF2121G Gangsta

给定一个长度为 $n$ 的二进制字符串 $s_1s_2\ldots s_n$。一个字符串被称为二进制字符串当且仅当它只包含 $0$ 和 $1$。 对于一个字符串 $p$，我们定义函数 $f(p)$ 为字符串 $p$ 中某个字符出现次数的最大值。例如，$f(00110) = 3$，$f(01) = 1$。 你需要计算所有满足 $1 \leq l \leq r \leq n$ 的区间 $[l, r]$，即所有子串 $s_ls_{l+1}\ldots s_r$ 的 $f(s_ls_{l+1}\ldots s_r)$ 之和。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示二进制字符串的长度。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由 $0$ 和 $1$ 组成，即二进制字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出所有区间 $[l, r]$ 的 $f(s_ls_{l+1}\ldots s_r)$ 之和。

在第一个测试用例中，字符串 $s$ 只有一个子串，$f(0) = 1$。 在第二个测试用例中，字符串 $s$ 的所有子串为 $0$、$01$、$1$，答案分别为 $1 + 1 + 1 = 3$。 在第三个测试用例中，字符串 $s$ 的所有子串为 $0$、$01$、$011$、$0110$、$1$、$11$、$110$、$1$、$10$、$0$，答案分别为 $1 + 1 + 2 + 2 + 1 + 2 + 2 + 1 + 1 + 1 = 14$。 由 ChatGPT 4.1 翻译