CF2077C.Binary Subsequence Value Sum

Last | Moment - onoken

对于一个二进制字符串 $^{\text{∗}}$ $v$，其分数定义为以下值的最大值：

$$\max_{0 \leq i \leq |v|} \left[ F(v, 1, i) \cdot F(v, i+1, |v|) \right]$$

其中 $F(v, l, r) = r - l + 1 - 2 \cdot \operatorname{zero}(v, l, r)$，这里 $\operatorname{zero}(v, l, r)$ 表示子串 $v_lv_{l+1}\ldots v_r$ 中 $\mathtt{0}$ 的数量。若 $l > r$，则 $F(v, l, r) = 0$。

给定一个长度为 $n$ 的二进制字符串 $s$ 和一个正整数 $q$。你需要处理 $q$ 次修改查询。

每次查询给出一个整数 $i$（$1 \leq i \leq n$），你必须翻转 $s_i$（将 $\mathtt{0}$ 改为 $\mathtt{1}$ 或 $\mathtt{1}$ 改为 $\mathtt{0}$）。每次修改后，计算 $s$ 所有非空子序列 $^{\text{†}}$ 的分数之和。

由于结果可能很大，请输出对 $998\,244\,353$ 取模后的答案。注意所有修改是持久化的。

$^{\text{∗}}$ 二进制字符串是仅由 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。

$^{\text{†}}$ 二进制字符串 $x$ 是 $y$ 的子序列，当且仅当 $x$ 可以通过删除 $y$ 中的若干字符（可能为零或全部）得到。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来描述每个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$）—— 分别表示字符串 $s$ 的长度和修改查询的数量。

第二行输入一个长度为 $n$ 的二进制字符串 $s$，由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成。

接下来 $q$ 行每行输入一个整数 $i$（$1 \leq i \leq n$），表示需要翻转 $s_i$ 的值。

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

对于每个测试用例，输出 $q$ 行，每行一个整数，表示修改后所有非空子序列的分数之和模 $998\,244\,353$ 的结果。

示例解释

第一个测试用例中，首次修改后 $s = \texttt{110}$。所有子序列的分数计算如下：

索引	子序列	分数
1	1	0
2	1	0
1, 2	11	1
3	0	0
1, 3	10	0
2, 3	10	0
1, 2, 3	110	0

总和为 $0 + 0 + 1 + 0 + 0 + 0 + 0 = 1$。

第二次修改后 $s = \texttt{111}$。所有子序列的分数计算如下：

索引	子序列	分数
1	1	0
2	1	0
1, 2	11	1
3	1	0
1, 3	11	1
2, 3	11	1
1, 2, 3	111	2

总和为 $0 + 0 + 1 + 0 + 1 + 1 + 2 = 5$。

翻译由 DeepSeek R1 完成