CF2267E Clean Substrings

对于长度为 $m$ 的二进制字符串 $t$，若对所有 $1 \le i < m$，都有 $t_i = t_{i+1}$，则称 $t$ 是“干净的”（clean）。 国家的首席工程师又有了新发现。他发明了一台智能机器人，该机器人可以对任意二进制字符串 $t$ 用一枚硬币执行以下操作： - 选择字符串 $t$ 的任意一个“干净子串” $^\text{∗}$。 - 翻转该子串的所有元素（$0$ 变为 $1$，$1$ 变为 $0$）。 定义字符串 $t$ 的美丽度（beauty）为：将其变为干净所需的最少硬币数。定义字符串 $t$ 的力量（power）为其所有子串美丽度之和。 现在给定一个长度为 $n$ 的二进制字符串 $s$。工程师的竞争者将对该字符串进行恰好 $q$ 次修改。每次修改描述为一个整数 $i$，表示将 $s_i$ 翻转。你的任务是计算字符串 $s$ 在每次修改前后的力量。 $^\text{∗}$ 字符串 $a$ 是字符串 $b$ 的子串，表示 $a$ 可以通过从 $b$ 的开头删除若干（可能为零或所有）字符，并从结尾删除若干（可能为零或所有）字符获得。

每组测试包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试组数。 每组测试的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$），分别表示二进制字符串的长度和修改次数。 第二行包含一个长度为 $n$ 的二进制字符串 $s$。 接下来的 $q$ 行，每行包含一个整数 $i$（$1 \le i \le n$），表示此次修改的位置。 保证所有测试组中所有 $n$ 的总和与所有 $q$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试，输出 $q+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$。 由 ChatGPT 5 翻译