CF1450H2 Multithreading (Hard Version)

本题的两个版本唯一的区别在于，简单版本中没有更新操作。 有 $n$ 个线轴放置在一个圆桌的边缘上。这些线轴有两种线：一种是黑色线，另一种是白色线。 对于任意两个同色的线轴，你可以用同色的线将它们以一条直线段连接起来。定义一次“匹配”为一种将线轴两两配对的方式，使得每个线轴恰好与另一个线轴配对。 “染色”是指为线轴分配颜色（白色或黑色）。如果一种染色方案中黑色线轴和白色线轴的数量均为偶数，则称该染色方案是“合法”的。 给定一种匹配方式，我们可以统计白线与黑线相交的次数。我们计算的是不同颜色的线段相交的对数，而不是交点的个数，因此如果多个不同颜色的线段在同一个点相交，这个交点会被多次计数。若 $c$ 是一种合法染色方案，记 $f(c)$ 为所有可能匹配方式中上述交点对数的最小值。  上图描述的圆圈染色为 bwbbbwww。按照图中所示的匹配方式，不同颜色的线段有一次相交。可以证明这是最小可能值，因此 $f(\text{bwbbbwww}) = 1$。现给定一个字符串 $s$，表示未完成的染色方案，其中线轴可能为黑色、白色或未染色。若通过给 $s$ 中未染色的线轴分配颜色（不改变其他线轴的颜色）可以得到染色方案 $c$，则称 $c$ 是 $s$-可达的。 在所有合法且 $s$-可达的染色方案中，等概率随机选择一个 $c$。请计算 $f(c)$ 的期望值。答案需要对 $998244353$ 取模。 接下来有 $m$ 次操作，每次将 $s$ 的某一位置的字符修改为新的颜色。每次操作后，你都需要重新计算 $f(c)$ 的期望值。 可以证明，每个答案都可以写成 $\frac{p}{q}$ 的形式，其中 $p$ 和 $q$ 互质且 $q\not\equiv 0\pmod{998244353}$。最终答案为 $(p\cdot q^{-1})$ 对 $998244353$ 取模的结果。

第一行包含两个整数 $n$ 和 $m$（$2\le n\le 2\cdot 10^5$，$n$ 为偶数，$0\le m\le 2\cdot 10^5$）——线轴数量和操作次数。 第二行包含一个长度为 $n$ 的字符串 $s$——表示线轴的初始染色方案。第 $i$ 个字符为 'w'、'b' 或 '?'，分别表示第 $i$ 个线轴为白色、黑色或未染色。 接下来的 $m$ 行，每行包含一个整数 $i$（$1 \leq i \leq n$）和一个字符 $c$（$c \in \{\text{w}, \text{b}, \text{?}\}$），表示将 $s$ 的第 $i$ 个字符修改为 $c$。 保证初始和每次操作后都至少存在一个未染色的线轴。

输出 $m+1$ 行：分别为初始状态及每次操作后的 $f(c)$ 的期望值，对 $998244353$ 取模。

第一个测试样例与图片对应。将 '?' 染为 'w' 不会得到合法染色，因为黑色线轴数量为奇数。因此唯一可达的合法染色为 'bwbbbwww'，且 $f(\text{bwbbbwww}) = 1$，所以期望值为 $1$。 第二个测试样例中，每次操作后的字符串依次为： 1. ????w?wb?? 2. ??????wb?? 3. ?w????wb?? 第三个测试样例中，每次操作后的字符串依次为： 1. ww?b 2. wb?b 3. wb?b 由 ChatGPT 4.1 翻译