Optimal Segmentation in a Two‐Player Piece Placing Game

In this game, two players, R and M, take turns placing chess pieces (black or white) on a 1×n board. Some cells already contain a black piece (B) or a white piece (W); the remaining m cells are empty (denoted by _). Before the game starts, both players know an operation sequence

[ O = [\langle c_1,x_1\rangle,; \langle c_2,x_2\rangle, ; \dots, ; \langle c_m,x_m\rangle] ]

where for each step i the tuple (\langle c_i,x_i\rangle) means that at cell position x_i (which is empty at that moment) player c_i (which is either R or M) will place a piece. When placing a piece the player may choose either black or white.

Once all moves are made the board is full. A maximal contiguous segment of same‐color pieces is defined as a pair \((l,r)\) (with \(1\le l\le r\le n\)) such that all pieces from the l‑th to the r‑th cell have the same color, and the piece immediately before and after the segment (if they exist) have the opposite color. Thus, the final number of segments equals

[ \text{segments} = 1 + \sum_{i=1}^{n-1} \mathbf{1}(p_i \neq p_{i+1}). ]

Player R wishes this number to be as high as possible, while player M wants it as low as possible. Assuming both play optimally, determine the final number of segments. It can be proved that the answer is uniquely determined.

Game Details

• The board is described by a string s of length n consisting of characters B, W, and _.
• If si=B or W, the cell is pre‐filled with that color.
• If si=_, that cell is empty and will eventually be filled by a move from the given operation sequence.

For an empty cell the eventual color is chosen by the player assigned to that cell (via the operation sequence). When a player makes a move, his decision affects the transition(s) with his cell’s neighbors (if any). In particular, if a cell has two neighbors, the same decision affects two adjacent boundaries. In a free (empty) segment (i.e. a maximal block of consecutive '_' characters) the players have a partisan game: each cell in that segment is controlled by either R or M (according to the operation sequence) and the payoff is the total number of adjacent pairs (including the edges with fixed neighbors, if they exist) with different colors. If a cell is on the edge of the board (or adjacent to a fixed cell) the corresponding boundary’s difference is counted if the colors differ.

The optimal play in each free segment (solved via standard minimax/dynamic programming) will yield a unique contribution to the total number of transitions. Adding these to the transitions between originally fixed adjacent cells (which are determined) and then adding 1 gives the final number of segments.

Note on Mathematical Notation: All formulas are given in \(\LaTeX\) format.

inputFormat

The input is given as follows:

1. A line containing the string s of length n (each character is either B, W, or _).
2. A line containing an integer m — the number of operations (which equals the number of '_' in s).
3. m lines follow. Each line contains a character and an integer separated by a space. The character is either R or M (denoting the player for that move) and the integer x (1-indexed) indicates the board position where the move is applied (this position is guaranteed to be empty at that moment).

You may assume that the operation sequence is valid.

outputFormat

Output a single integer — the final number of maximal same‐color contiguous segments on the board if both players play optimally.

sample

B_W
1
R 2

2