整洁子串AI (CI翻译)
A binary string $t$ of length $m$ is called clean if $t_i = t_{i+1}$ for all $1\le i\lt m$.
长度为 $m$ 的二进制字符串 $t$ 被称为整洁，当且仅当对于所有 $1\le i\lt m$，都有 $t_i = t_{i+1}$。AI (CI翻译)
The chief engineer of the country has made another discovery. He invented a smart robot that can perform the following operation on any binary string $t$ for one coin:
这个国家的总工程师又有了新的发现。他发明了一台智能机器人，只需花费一枚硬币，就可以对任意二进制字符串 $t$ 执行以下操作：AI (CI翻译)
- Choose any clean substring
$^{\text{∗}}$of the string$t$. - Invert all elements of the substring (change
$0$to$1$and vice versa).
- 选择字符串
$t$的任意整洁子串$^{\text{∗}}$。 - 翻转该子串中的所有元素（将 0 变为 1，反之亦然）。
Define the beauty of a string $t$ as the minimum number of coins needed to make it clean. Define the power of a string $t$ as the sum of the beauties of all its substrings.
定义字符串 $t$ 的美丽度为将其变为整洁所需的最少硬币数。定义字符串 $t$ 的能量为其所有子串的美丽度之和。AI (CI翻译)
You are given a binary string $s$ of length $n$. The engineer's competitors are going to modify the string exactly $q$ times. Each modification is described by one number $i$. After the modification, $s_i$ is inverted. Your task is to compute the power of the string $s$ before and after each modification.
现在给定一个长度为 $n$ 的二进制字符串 $s$。工程师的竞争对手将对该字符串进行恰好 $q$ 次修改。每次修改由一个数字 $i$ 描述。修改后，$s_i$ 将被翻转。你的任务是计算字符串 $s$ 在修改前以及每次修改后的能量。AI (CI翻译)
$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
$^{\text{∗}}$如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干个（可能为零个或全部）字符，并从结尾删除若干个（可能为零个或全部）字符得到，则称 $a$ 是 $b$ 的子串。AI (CI翻译)
Input
输入
AI (CI翻译)Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来给出各测试用例的描述。AI (CI翻译)
The first line of each test case contains two integers $n$ and $q$ ($1\le n, q\le 2\cdot 10^5$) — the length of the binary string and the number of modifications.
每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\le n, q\le 2\cdot 10^5$）——二进制字符串的长度以及修改次数。AI (CI翻译)
The second line of each test case contains the binary string $s$.
每个测试用例的第二行包含二进制字符串 $s$。AI (CI翻译)
The next $q$ lines of each test case contain one integer $i$ ($1\le i\le n$) — the description of the modifications.
接下来的 $q$ 行中，每行包含一个整数 $i$（$1\le i\le n$）——表示一次修改。AI (CI翻译)
It is guaranteed that the sum of all $n$ values and the sum of all $q$ values over all test cases do not exceed $2\cdot 10^5$.
保证所有测试用例的 $n$ 之和以及所有测试用例的 $q$ 之和均不超过 $2\cdot 10^5$。AI (CI翻译)
Output
输出
AI (CI翻译)For each test case, output $q + 1$ integers separated by spaces — the answer before the modifications and after each modification of the string.
对于每个测试用例，输出 $q + 1$ 个由空格分隔的整数——分别表示修改前以及每次修改后的答案。AI (CI翻译)
Note
说明
AI (CI翻译)Consider the first test case.
考虑第一个测试用例。AI (CI翻译)
Before the modifications, the string $s$ is 110. The power of the string is $2$:
修改前，字符串 $s$ 为 110。该字符串的能量为 $2$：AI (CI翻译)
- The beauty of substring
$s[1, 1]$is 0. - The beauty of substring
$s[2, 2]$is 0. - The beauty of substring
$s[3, 3]$is 0. - The beauty of substring
$s[1, 2]$is 0. - The beauty of substring
$s[2, 3]$is 1. - The beauty of substring
$s[1, 3]$is 1.
- 子串
$s[1, 1]$的美丽度为 0。 - 子串
$s[2, 2]$的美丽度为 0。 - 子串
$s[3, 3]$的美丽度为 0。 - 子串
$s[1, 2]$的美丽度为 0。 - 子串
$s[2, 3]$的美丽度为 1。 - 子串
$s[1, 3]$的美丽度为 1。
After the modification, the string $s$ is
修改后，字符串 $s$ 为AI (CI翻译)
100
100AI (CI翻译)
. Now the
。现在字符串的AI (CI翻译)
power
能量AI (CI翻译)
is $2$:
为 $2$：AI (CI翻译)
- The beauty of substring
$s[1, 1]$is 0. - The beauty of substring
$s[2, 2]$is 0. - The beauty of substring
$s[3, 3]$is 0. - The beauty of substring
$s[1, 2]$is 1. - The beauty of substring
$s[2, 3]$is 0. - The beauty of substring
$s[1, 3]$is 1.
- 子串
$s[1, 1]$的美丽度为 0。 - 子串
$s[2, 2]$的美丽度为 0。 - 子串
$s[3, 3]$的美丽度为 0。 - 子串
$s[1, 2]$的美丽度为 1。 - 子串
$s[2, 3]$的美丽度为 0。 - 子串
$s[1, 3]$的美丽度为 1。
样例
4
3 1
110
2
4 2
1010
1
2
8 4
10101110
3
5
2
3
10 5
1100101110
1
6
10
7
3
2 2
7 5 5
36 23 22 25 26
61 66 41 35 59 60
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。