← 返回题目列表

Codeforces · 2121/G

G. 黑帮

中文机器翻译题面 查看原题

给定一个二进制字符串 $$$s_1s_2 \ldots s_n$$$,长度为 $$$n$$$。如果字符串 $$$s$$$ 仅由零和一组成,则称为二进制字符串。

对于字符串 $$$p$$$,我们将函数 $$$f(p)$$$ 定义为字符串 $$$p$$$ 中任何字符出现的最大次数。例如,$$$f(00110) = 3$$$,$$$f(01) = 1$$$。

您需要找到所有对 $$$1 \leq l \leq r \leq n$$$ 的总和 $$$f(s_ls_{l+1} \ldots s_r)$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是他们的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 二进制字符串的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串,由$$$0$$$s和$$$1$$$s组成——二进制字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出所有对 $$$1 \leq l \leq r \leq n$$$ 的总和 $$$f(s_ls_{l+1} \ldots s_r)$$$。

示例

输入
复制

6
1
0
2
01
4
0110
6
110001
8
10011100
11
01011011100

输出
复制

1
3
14
40
78
190

注意

在第一个测试用例中,字符串 $$$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$$$。