← 返回题目列表

Codeforces · 1694/B

B. 偏执字符串

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

如果我们可以通过以任意顺序执行以下两种操作 $$$m-1$$$ 次来获得长度为 $$$1$$$ 的字符串,那么我们称长度为 $$$m$$$ 的二进制字符串 $$$T$$$ 为偏执,索引从 $$$1$$$ 到 $$$m$$$ :

- 选择 $$$T$$$ 中等于 01 的任何子字符串,然后将其替换为 1。
- 选择$$$T$$$中任意等于10的子串,然后将其替换为0。例如,如果$$$T = $$$ 001,我们可以选择子串$$$[T_2T_3]$$$并执行第一个操作。所以我们得到$$$T = $$$ 01。

给定一个二进制字符串 $$$S$$$,长度为 $$$n$$$,索引从 $$$1$$$ 到 $$$n$$$。求整数对 $$$(l, r)$$$ $$$1 \le l \le r \le n$$$ 使得 $$$S[l \ldots r]$$$ ($$$S$$$ 从 $$$l$$$ 到 $$$r$$$ 的子串)是一个偏执串。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$S$$$ 的大小。

每个测试用例的第二行包含一个二进制字符串 $$$S$$$,包含 $$$n$$$ 个字符 $$$S_1S_2 \ldots S_n$$$。 (对于每个 $$$1 \le i \le n$$$,$$$S_i = $$$ 0 或 $$$S_i = $$$ 1)

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

输出

对于每个测试用例,输出整数对 $$$(l, r)$$$ $$$1 \le l \le r \le n$$$ 的数量,使得 $$$S[l \ldots r]$$$ ($$$S$$$ 从 $$$l$$$ 到 $$$r$$$ 的子字符串)是偏执字符串。

示例

输入 #1

5
1
1
2
01
3
100
4
1001
5
11111

输出 #1

1
3
4
8
5

注意

在第一个示例中,$$$S$$$ 的长度已经为 $$$1$$$,不需要任何操作。

在第二个示例中,$$$S$$$ 的所有子字符串都是偏执的。对于整个字符串,执行第一个操作就足够了。

在第三个示例中,$$$S$$$ 的所有子字符串都是偏执的,除了 $$$[S_2S_3]$$$(因为我们无法对其执行任何操作)和 $$$[S_1S_2S_3]$$$(整个字符串)。