CF2077C Binary Subsequence Value Sum

[Last | Moment - onoken](https://www.youtube.com/watch?v=l_fXX3Y0Pis) 对于一个二进制字符串 $^{\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 完成