Paranoid String

题意翻译

对一个字符串，有以下两种操作： - 将子串 01 替换为 1 - 将子串 10 替换为 0 $t$ 组数据，每组给定一个长度为 $n$ 的 01 串 $S$ 。求 $S$ 的子串个数，满足经过若干次操作，可将该子串长度变为 $1$ 。 $1\le t\le 1000,1\le n\le 2\times 10^5,\sum n\le 2\times 10^5$

题目描述

Let's call a binary string $ T $ of length $ m $ indexed from $ 1 $ to $ m $ paranoid if we can obtain a string of length $ 1 $ by performing the following two kinds of operations $ m-1 $ times in any order : - Select any substring of $ T $ that is equal to 01, and then replace it with 1. - Select any substring of $ T $ that is equal to 10, and then replace it with 0.For example, if $ T = $ 001, we can select the substring $ [T_2T_3] $ and perform the first operation. So we obtain $ T = $ 01. You are given a binary string $ S $ of length $ n $ indexed from $ 1 $ to $ n $ . Find the number of pairs of integers $ (l, r) $ $ 1 \le l \le r \le n $ such that $ S[l \ldots r] $ (the substring of $ S $ from $ l $ to $ r $ ) is a paranoid string.

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of $ S $ . The second line of each test case contains a binary string $ S $ of $ n $ characters $ S_1S_2 \ldots S_n $ . ( $ S_i = $ 0 or $ S_i = $ 1 for each $ 1 \le i \le n $ ) It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output the number of pairs of integers $ (l, r) $ $ 1 \le l \le r \le n $ such that $ S[l \ldots r] $ (the substring of $ S $ from $ l $ to $ r $ ) is a paranoid string.

输入输出样例

输入样例 #1

5
1
1
2
01
3
100
4
1001
5
11111

输出样例 #1

1
3
4
8
5

说明

In the first sample, $ S $ already has length $ 1 $ and doesn't need any operations. In the second sample, all substrings of $ S $ are paranoid. For the entire string, it's enough to perform the first operation. In the third sample, all substrings of $ S $ are paranoid except $ [S_2S_3] $ , because we can't perform any operations on it, and $ [S_1S_2S_3] $ (the entire string).

**题目大意：**

- **题目名称：** 恐慌字符串

- **题意简述：** 给定一个只包含0和1的字符串，有两种操作：
- 将子串“01”替换为“1”；
- 将子串“10”替换为“0”。
需要找出字符串的所有子串中，有多少个子串可以通过上述操作最终变为长度为1的字符串。

- **输入数据：**
- 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $），表示字符串的长度。
- 第二行包含一个长度为 $ n $ 的01字符串。
- 保证所有测试用例的字符串长度之和不超过 $ 2 \times 10^5 $。

- **输出数据：** 对于每个测试用例，输出一个整数，表示满足条件的子串个数。

- **示例：**
- 输入样例：
```
5
1
1
2
01
3
100
4
1001
5
11111
```
- 输出样例：
```
1
3
4
8
5
```

- **说明：** 对于第一个样例，字符串 $ S $ 的长度已经是1，不需要任何操作。对于第二个样例，字符串 $ S $ 的所有子串都是恐慌字符串。对于第三个样例，除了子串 $ [S_2S_3] $ 以外的所有子串都是恐慌字符串，因为对于这个子串我们无法执行任何操作。

- **题目描述：** 如果一个二进制字符串 $ T $ 的长度为 $ m $，并且可以通过进行 $ m-1 $ 次以下两种类型的操作以任意顺序得到长度为1的字符串，那么我们称该字符串为恐慌字符串：
- 选择 $ T $ 的任意等于01的子串，并将其替换为1。
- 选择 $ T $ 的任意等于10的子串，并将其替换为0。
例如，如果 $ T = 001 $，我们可以选择子串 $ [T_2T_3] $ 并执行第一个操作。所以我们得到 $ T = 01 $。
给定一个长度为 $ n $ 的二进制字符串 $ S $，找出满足 $ S[l \ldots r] $（从 $ l $ 到 $ r $ 的 $ S $ 的子串）为恐慌字符串的整数对 $ (l, r) $ 的数量。**题目大意：** - **题目名称：** 恐慌字符串 - **题意简述：** 给定一个只包含0和1的字符串，有两种操作： - 将子串“01”替换为“1”； - 将子串“10”替换为“0”。 需要找出字符串的所有子串中，有多少个子串可以通过上述操作最终变为长度为1的字符串。 - **输入数据：** - 第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 $ n $（$ 1 \le n \le 2 \times 10^5 $），表示字符串的长度。 - 第二行包含一个长度为 $ n $ 的01字符串。 - 保证所有测试用例的字符串长度之和不超过 $ 2 \times 10^5 $。 - **输出数据：** 对于每个测试用例，输出一个整数，表示满足条件的子串个数。 - **示例：** - 输入样例： ``` 5 1 1 2 01 3 100 4 1001 5 11111 ``` - 输出样例： ``` 1 3 4 8 5 ``` - **说明：** 对于第一个样例，字符串 $ S $ 的长度已经是1，不需要任何操作。对于第二个样例，字符串 $ S $ 的所有子串都是恐慌字符串。对于第三个样例，除了子串 $ [S_2S_3] $ 以外的所有子串都是恐慌字符串，因为对于这个子串我们无法执行任何操作。 - **题目描述：** 如果一个二进制字符串 $ T $ 的长度为 $ m $，并且可以通过进行 $ m-1 $ 次以下两种类型的操作以任意顺序得到长度为1的字符串，那么我们称该字符串为恐慌字符串： - 选择 $ T $ 的任意等于01的子串，并将其替换为1。 - 选择 $ T $ 的任意等于10的子串，并将其替换为0。 例如，如果 $ T = 001 $，我们可以选择子串 $ [T_2T_3] $ 并执行第一个操作。所以我们得到 $ T = 01 $。 给定一个长度为 $ n $ 的二进制字符串 $ S $，找出满足 $ S[l \ldots r] $（从 $ l $ 到 $ r $ 的 $ S $ 的子串）为恐慌字符串的整数对 $ (l, r) $ 的数量。