BinaryStringForces

题意翻译

你有一个只由 $0$ 和 $1$ 组成的字符串。我们定义一次操作为选取一对相邻的极长相同子段（必然一个为若干 $0$，一个为若干 $1$），设连续 $0,1$ 的个数分别为 $a,b$ ，若$a\le b$ 则将其中 $0$ 变成 $1$ ；反之则将其中 $1$ 变成 $0$ 。问你的字符串有多少连续子段可以经过若干操作全变成 $1$ 。

题目描述

You are given a binary string $ s $ of length $ n $ . We define a maximal substring as a substring that cannot be extended while keeping all elements equal. For example, in the string $ 11000111 $ there are three maximal substrings: $ 11 $ , $ 000 $ and $ 111 $ . In one operation, you can select two maximal adjacent substrings. Since they are maximal and adjacent, it's easy to see their elements must have different values. Let $ a $ be the length of the sequence of ones and $ b $ be the length of the sequence of zeros. Then do the following: - If $ a \ge b $ , then replace $ b $ selected zeros with $ b $ ones. - If $ a < b $ , then replace $ a $ selected ones with $ a $ zeros. As an example, for $ 1110000 $ we make it $ 0000000 $ , for $ 0011 $ we make it $ 1111 $ . We call a string being good if it can be turned into $ 1111...1111 $ using the aforementioned operation any number of times (possibly, zero). Find the number of good substrings among all $ \frac{n(n+1)}{2} $ non-empty substrings of $ s $ .

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the string $ s $ . The second line of each test case contains the binary string $ s $ of length $ n $ . It is guaranteed that sum of $ n $ across all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the number of good substrings.

输入输出样例

输入样例 #1

4
6
100011
3
101
5
11111
6
010101

输出样例 #1

8
5
15
18

说明

Let's define a substring from index $ l $ to index $ r $ as $ [l, r] $ . For the first test case, the good substrings are: - $ [1,1] $ , - $ [1,2] $ , - $ [3,6] $ , - $ [4,5] $ , - $ [4,6] $ , - $ [5,5] $ , - $ [5,6] $ , - $ [6,6] $ . In the second test case, all substrings are good except $ [2,2] $ . In the third test case, all substrings are good.

**题目大意**：

给定一个长度为 $ n $ 的由 '0' 和 '1' 组成的字符串 $ s $。定义一个极大子串为不能在保持所有元素相等的情况下扩展的子串。例如，在字符串 "11000111" 中有三个极大子串："11"、"000" 和 "111"。

一次操作可以选取两个相邻的极大子串。由于它们是极大且相邻的，它们的元素值必然不同。设 $ a $ 为连续 '1' 的个数，$ b $ 为连续 '0' 的个数。然后执行以下操作：

- 如果 $ a \ge b $，则将 $ b $ 个 '0' 替换为 '1'。
- 如果 $ a < b $，则将 $ a $ 个 '1' 替换为 '0'。

如果一个字符串可以通过上述操作任意次数（可能为零）变成全 '1' 的字符串，则称该字符串为“好字符串”。求出在所有 $ \frac{n(n+1)}{2} $ 个非空子串中有多少个好字符串。

**输入输出格式**：

**输入格式**：
- 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 $ n $（$ 1 \le n \le 2 \cdot 10^5 $）——字符串 $ s $ 的长度。
- 第二行包含一个长度为 $ n $ 的二进制字符串 $ s $。

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

**输出格式**：
- 对于每个测试用例，输出一个整数——好字符串的数量。

**输入输出样例**：

**输入样例 #1**：
```
4
6
100011
3
101
5
11111
6
010101
```

**输出样例 #1**：
```
8
5
15
18
```**题目大意**： 给定一个长度为 $ n $ 的由 '0' 和 '1' 组成的字符串 $ s $。定义一个极大子串为不能在保持所有元素相等的情况下扩展的子串。例如，在字符串 "11000111" 中有三个极大子串："11"、"000" 和 "111"。 一次操作可以选取两个相邻的极大子串。由于它们是极大且相邻的，它们的元素值必然不同。设 $ a $ 为连续 '1' 的个数，$ b $ 为连续 '0' 的个数。然后执行以下操作： - 如果 $ a \ge b $，则将 $ b $ 个 '0' 替换为 '1'。 - 如果 $ a < b $，则将 $ a $ 个 '1' 替换为 '0'。 如果一个字符串可以通过上述操作任意次数（可能为零）变成全 '1' 的字符串，则称该字符串为“好字符串”。求出在所有 $ \frac{n(n+1)}{2} $ 个非空子串中有多少个好字符串。 **输入输出格式**： **输入格式**： - 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 $ n $（$ 1 \le n \le 2 \cdot 10^5 $）——字符串 $ s $ 的长度。 - 第二行包含一个长度为 $ n $ 的二进制字符串 $ s $。 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。 **输出格式**： - 对于每个测试用例，输出一个整数——好字符串的数量。 **输入输出样例**： **输入样例 #1**： ``` 4 6 100011 3 101 5 11111 6 010101 ``` **输出样例 #1**： ``` 8 5 15 18 ```