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.

题意翻译

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