CF1450H2.Multithreading (Hard Version)

The only difference between the two versions of the problem is that there are no updates in the easy version.

There are $n$ spools of thread placed on the rim of a circular table. The spools come in two types of thread: the first thread is black and the second thread is white.

For any two spools of the same color, you can attach them with a thread of that color in a straight line segment. Define a matching as a way to attach spools together so that each spool is attached to exactly one other spool.

Coloring is an assignment of colors (white and black) to the spools. A coloring is called valid if it has at least one matching. That is if the number of black spools and the number of white spools are both even.

Given a matching, we can find the number of times some white thread intersects some black thread. We compute the number of pairs of differently colored threads that intersect instead of the number of intersection points, so one intersection point may be counted multiple times if different pairs of threads intersect at the same point. If $c$ is a valid coloring, let $f(c)$ denote the minimum number of such intersections out of all possible matchings.

The circle above is described by the coloring bwbbbwww. After matching the spools as shown, there is one intersection between differently colored threads. It can be proven that it is the minimum possible, so $f(\text{bwbbbwww}) = 1$.

You are given a string $s$ representing an unfinished coloring, with black, white, and uncolored spools. A coloring $c$ is called $s$-reachable if you can achieve it by assigning colors to the uncolored spools of $s$ without changing the others.

A coloring $c$ is chosen uniformly at random among all valid, $s$-reachable colorings. Compute the expected value of $f(c)$. You should find it by modulo $998244353$.

There will be $m$ updates to change one character of $s$. After each update, you should again compute the expected value of $f(c)$.

We can show that each answer can be written in the form $\frac{p}{q}$ where $p$ and $q$ are relatively prime integers and $q\not\equiv 0\pmod{998244353}$. The answer by modulo $998244353$ is equal to $(p\cdot q^{-1})$ modulo $998244353$.

两个版本问题的唯一区别在于，简单版本中没有更新操作。

有 $n$ 个线轴放置在一个圆形桌子的边缘。线轴包含两种颜色的线：第一种为黑色，第二种为白色。

对于任意两个同色线轴，你可以用该颜色的线以直线段将其连接起来。定义一个匹配（matching）为一种连接线轴的方式，使得每个线轴恰好与另一个线轴相连。

着色（coloring）是指将颜色（白色或黑色）分配给各个线轴。若某着色方案存在至少一个匹配，则称其为合法着色（valid coloring）。即：黑色线轴数量与白色线轴数量均为偶数。

给定一个匹配，我们可以计算某条白线与某条黑线相交的次数。我们统计的是不同颜色线段对的相交对数，而非交点个数；因此，若多个不同颜色线段对在同一点相交，该交点会被多次计数。若 $c$ 是一个合法着色，则记 $f(c)$ 为在所有可能匹配中，此类相交对数的最小值。

上图所示圆对应着色 bwbbbwww。按图中方式匹配线轴后，存在一对不同颜色线段相交。可以证明这是最小可能值，故 $f(\text{bwbbbwww}) = 1$。

你将得到一个字符串 $s$，表示一个未完成的着色，其中包含黑色、白色及未着色的线轴。若着色 $c$ 可通过对 $s$ 中未着色线轴赋色（其余位置颜色不变）而得到，则称 $c$ 是 $s$-可达的（$s$-reachable）。

在所有合法且 $s$-可达的着色中，随机均匀选取一个着色 $c$。请计算 $f(c)$ 的期望值（expected value）。答案需对 $998244353$ 取模。

接下来会有 $m$ 次更新，每次更新将 $s$ 中的一个字符修改为另一字符。每次更新后，你都需要重新计算 $f(c)$ 的期望值。

可以证明，每个答案均可表示为 $\frac{p}{q}$ 的形式，其中 $p$ 与 $q$ 互质，且 $q \not\equiv 0 \pmod{998244353}$。该答案对 $998244353$ 取模的结果即为 $(p \cdot q^{-1}) \bmod 998244353$。

The first line contains two integers $n$, $m$ ($2\le n\le 2\cdot 10^5$, $n$ is even, $0\le m\le 2\cdot 10^5$) — the number of spools and the number of updates, respectively.

The second line contains a string $s$ of length $n$ — the unfinished coloring of the spools. The $i$-th character will be 'w', 'b', or '?', describing if the $i$-th spool is white, black, or uncolored, respectively.

Each of the next $m$ lines contains an integer $i$ ($1 \leq i \leq n$) — the position of the character in $s$ to be updated, and a character $c$ ($c \in {\text{w}, \text{b}, \text{?}}$) — the new color of the spool $i$ after the update.

It is guaranteed there exists at least one uncolored spool initially and after each update.

第一行包含两个整数 $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$）——表示字符串 $s$ 中待更新的字符位置，以及一个字符 $c$（$c \in \{\text{w}, \text{b}, \text{?}\}$）——表示第 $i$ 个线轴在此次更新后的新颜色。

保证初始时及每次更新后均至少存在一个未染色的线轴。

Print $m+1$ lines: the expected value of $f(c)$ initially and after each update. All values should be found by modulo $998244353$.

输出 $m+1$ 行：函数 $f(c)$ 的初始期望值以及每次更新后的期望值。所有数值均需对 $998244353$ 取模。

The first test corresponds closely to the image. Coloring '?' as 'w' does not create a valid coloring because the number of black spools is odd. Then the only reachable valid coloring is 'bwbbbwww' and $f(\text{bwbbbwww}) = 1$, so the expected value is $1$.

In the second test, the string after each update is:

1. ????w?wb??
2. ??????wb??
3. ?w????wb??

In the third test, the string after each update is:

1. ww?b
2. wb?b
3. wb?b

第一个测试用例与图片高度对应。将 '?' 染成 'w' 无法得到合法染色，因为黑色线轴的数量为奇数。因此唯一可达的合法染色为 'bwbbbwww'，且 $f(\text{bwbbbwww}) = 1$，故期望值为 $1$。

第二个测试用例中，每次更新后的字符串依次为：

1. ????w?wb??
2. ??????wb??
3. ?w????wb??

第三个测试用例中，每次更新后的字符串依次为：

1. ww?b
2. wb?b
3. wb?b