P10608 Two-Player Game

After finishing her paper, Renko finally realizes her mistake of burying herself in work and ignoring Merry for so long. She decides to invite Merry out and devises an interesting two-player game.

Renko has designed a two-player game with two players, Little R and Little M, following these rules: There is a $1 \times n$ chessboard. Initially, the board has some black pieces, white pieces, and $m$ empty cells. The initial state of the board is described by a string $s$ of length $n$, where: - `B` indicates a black piece, - `W` indicates a white piece, - `_` indicates an empty cell. **Note: The board may have no empty cells.** Before the game starts, both players receive an operation sequence $O = [\langle c_1, x_1 \rangle, \langle c_2, x_2 \rangle, \ldots, \langle c_m, x_m \rangle]$, where each pair $\langle c_i, x_i \rangle$ satisfies: - $c_i \in \{\mathtt{R}, \mathtt{M}\}$, - $x_i$ is an empty cell at step $i$. This sequence is public, meaning both players know who will place a piece and where at each step. During the game, players follow the operation sequence. In the $i$-th step, player $c_i$ places a piece (black or white, chosen by the player) at position $x_i$. By the end of the game, every cell will have exactly one piece. Little R aims to **maximize** the number of **maximal consecutive monochromatic segments**$^*$, while Little M aims to **minimize** it. Determine the final number of segments when both play optimally. It can be proven that the answer is unique. **Definition**: A maximal consecutive monochromatic segment is a pair $(l, r)$ where $l \leq r$, such that: - All pieces from the $l$-th to $r$-th position are the same color. - The $(l-1)$-th piece (if exists) and the $(r+1)$-th piece (if exists) are of a different color.

- The first line contains two integers $n$ and $m$, where $m$ is the number of empty cells. - The second line contains a string $s$ of length $n$, describing the initial board state. - The next $m$ lines each contain a character $c_i$ and an integer $x_i$, describing the player and the position for the $i$-th step.

Output one integer: the number of maximal consecutive monochromatic segments when both players act optimally.

### Explanation #### Sample #1 The final board is `BWW`, which is optimal for both players. The number of segments is $2$. #### Sample #2 Little R (controlling the first two steps) will place different colors to maximize segments. Little M then places any color. One possible final state is `BWW` with $2$ segments. This sample satisfies **Special Property B**. #### Sample #3 The final board is `BWBWB` with $5$ segments. This sample satisfies **Special Property A**. ### Constraints **Bundled testing is used.** $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n,m \leq} & \textbf{Special Property} & \textbf{Subtask Dependencies} \cr\hline 1 & 10 & 20 & - & - \cr\hline 2 & 10 & 2 \times 10^5 & \mathbf{A} & - \cr\hline 3 & 20 & 2 \times 10^5 & \mathbf{B} & - \cr\hline 4 & 20 & 10^3 & - & 1 \cr\hline 5 & 40 & 2 \times 10^5 & - & 1,2,3,4 \cr\hline \end{array} $$ **Special Properties**: - **A**: All $c_i$ are either `R` or `M`. - **B**: All characters in $s$ are `_`. For all data: $0 \leq m \leq 2 \times 10^5$, $1 \leq n \leq 2 \times 10^5$, $m \leq n$, and $s_i \in \{\mathtt{B}, \mathtt{W}, \mathtt{\_}\}$. --- Translated by DeepSeek R1