CF2267E.Clean Substrings

A binary string $t$ of length $m$ is called clean if $t_i = t_{i+1}$ for all $1\le i\lt m$.

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:

• Choose any clean substring$^{\text{∗}}$ of the string $t$.
• Invert all elements of the substring (change $0$ to $1$ and vice versa).

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.

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.

$^{\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.

长度为 $m$ 的二进制字符串 $t$ 被称为洁净的，当且仅当对所有 $1 \le i < m$，均有 $t_i = t_{i+1}$。

该国总工程师又有一项新发现：他发明了一种智能机器人，该机器人可以对任意二进制字符串 $t$ 执行如下操作（每次消耗一枚硬币）：

• 任选 $t$ 的一个洁净子串$^{\text{∗}}$；
• 将该子串中所有元素取反（即 $0$ 变为 $1$，$1$ 变为 $0$）。

定义字符串 $t$ 的美观度为使其变为洁净字符串所需的最少硬币数。定义字符串 $t$ 的威力为 $t$ 的所有子串的美观度之和。

现给定一个长度为 $n$ 的二进制字符串 $s$。总工程师的竞争对手将恰好对字符串执行 $q$ 次修改。每次修改由一个整数 $i$ 描述：修改后，$s_i$ 被取反。你的任务是在每次修改之前及之后，分别计算字符串 $s$ 的威力。

$^{\text{∗}}$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可通过从 $b$ 的开头删除若干（可能为零或全部）字符、并从 $b$ 的末尾删除若干（可能为零或全部）字符而得到。

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.

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.

The second line of each test case contains the binary string $s$.

The next $q$ lines of each test case contain one integer $i$ ($1\le i\le n$) — the description of the modifications.

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\le n, q\le 2\cdot 10^5$）—— 分别表示二进制字符串的长度和修改操作的次数。

每个测试用例的第二行包含二进制字符串 $s$。

每个测试用例接下来的 $q$ 行，每行包含一个整数 $i$（$1\le i\le n$）—— 表示一次修改操作的位置。

保证所有测试用例的 $n$ 值之和与所有测试用例的 $q$ 值之和均不超过 $2\cdot 10^5$。

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$ 个整数（以空格分隔）——即字符串修改前的答案，以及每次字符串修改后的答案。

Consider the first test case.

Before the modifications, the string $s$ is 110. The power of the string is $2$:

• 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.

After the modification, the string $s$ is 100. Now the power is $2$:

• 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$ 为 110。该字符串的“能量”为 $2$：

• 子串 $s[1, 1]$ 的“优美度”为 0。
• 子串 $s[2, 2]$ 的“优美度”为 0。
• 子串 $s[3, 3]$ 的“优美度”为 0。
• 子串 $s[1, 2]$ 的“优美度”为 0。
• 子串 $s[2, 3]$ 的“优美度”为 1。
• 子串 $s[1, 3]$ 的“优美度”为 1。

修改后，字符串 $s$ 变为 100。此时“能量”仍为 $2$：

• 子串 $s[1, 1]$ 的“优美度”为 0。
• 子串 $s[2, 2]$ 的“优美度”为 0。
• 子串 $s[3, 3]$ 的“优美度”为 0。
• 子串 $s[1, 2]$ 的“优美度”为 1。
• 子串 $s[2, 3]$ 的“优美度”为 0。
• 子串 $s[1, 3]$ 的“优美度”为 1。