P15456 [JOI 2026 SemiFinal] Strange Machine / Strange Machine

You have $N$ tiles, numbered from $1$ to $N$. Each tile has a front side and a back side, and each side is colored either black or white. Here, black is represented by the character `'B'`, and white is represented by the character `'W'`. For tile $i$ ($1 \le i \le N$), its front-side color is given by the $i$-th character of the string $S$, and its back-side color is given by the $i$-th character of the string $T$. Uzbekistan is famous for its historical buildings decorated with tiles. After visiting mosques and madrasas in Uzbekistan, you were fascinated by these beautiful buildings and bought a strange machine. This machine has a platform on the left and a platform on the right. By placing one tile on each platform, you can exchange these two tiles for one new tile. Let the tile placed on the left platform be $a$, and the tile placed on the right platform be $b$. The new tile $c$ obtained from $a$ and $b$ satisfies the following: - The front-side color of $c$: it is black if the back-side color of $a$ is the same as the front-side color of $b$; otherwise, it is white. - The back-side color of $c$: it is black if the front-side color of $a$ is the same as the back-side color of $b$; otherwise, it is white. You plan to use these $N$ tiles and the strange machine to do the following activities over $Q$ days. On day $j$ ($1 \le j \le Q$), the activity is either type 1 or type 2: - **Type 1**: Change the front-side color of tile $X_j$ to the color represented by the character $Y_j$, and change the back-side color of tile $X_j$ to the color represented by the character $Z_j$. Here $Y_j, Z_j$ are `'B'` or `'W'`. - **Type 2**: Arrange tiles $L_j, L_j+1, \dots, R_j$ in this order into a row from left to right. For this row, you may perform the following operation any number of times (from $0$ up to $R_j - L_j$ times), and then determine whether it is possible to make the number of tiles whose front side is white in the row equal to exactly $M_j$: - Choose two adjacent tiles in the row and remove them from the row. Put the tile that was originally on the left onto the left platform of the machine, and the one originally on the right onto the right platform. Exchange them for one new tile, and then insert the new tile back into the position where the two tiles were. Given the initial tile information and the activities for each day, write a program to output the answer for all type 2 activities.

Input is given from standard input in the following format: $N$ $S$ $T$ $Q$ (Query 1) (Query 2) $\vdots$ (Query $Q$) Each (Query $j$) ($1 \le j \le Q$) contains several space-separated integers or characters. The first value is an integer $1$ or $2$, denoted by $P_j$, and the rest of the line is one of the following: - If $P_j = 1$, then it is followed by an integer $X_j$ and two characters $Y_j, Z_j$ in this order. This means the activity on day $j$ is type 1: change the front-side color of tile $X_j$ to the color represented by $Y_j$, and change the back-side color to the color represented by $Z_j$. Here $Y_j, Z_j$ are `B` or `W`. - If $P_j = 2$, then it is followed by three integers $L_j, R_j, M_j$ in this order. This means the activity on day $j$ is type 2: arrange tiles $L_j, L_j+1, \dots, R_j$ in order into a row from left to right, and determine whether it is possible (using the operations) to make the number of tiles whose front side is white in the row exactly $M_j$.

For all $j$ such that $P_j = 2$ ($1 \le j \le Q$), output one line per query in increasing order of $j$: output `Yes` if it is possible to make the number of tiles whose front side is white in the row exactly $M_j$, and output `No` otherwise.

#### Sample Explanation 1 - Day 1: Arrange tiles $3,4$ in this order into a row from left to right. If you do not perform any operation, only tile $3$ has a white front side, so it is possible to make the number of tiles with a white front side exactly $1$. Therefore output `Yes`. - Day 2: Arrange tiles $1,2$ in this order into a row. If you choose tiles $1$ and $2$ and perform the operation once, the resulting row contains one tile whose front and back sides are both black, so it is possible to make the number of tiles with a white front side exactly $0$. Therefore output `Yes`. - Day 3: Change both the front and back sides of tile $3$ to black. - Day 4: Arrange tiles $3,4$ into a row. It can be proven that it is impossible to make the number of tiles with a white front side exactly $2$ by using the operations. Therefore output `No`. - Day 5: Arrange tiles $2,3,4$ into a row. If you first choose tiles $3$ and $4$ and perform the operation once, the row will contain two tiles: tile $2$ on the left and a new tile (whose front and back sides are both black) on the right. Then choose these two tiles and perform the operation once more; the row will contain one tile whose front side is white and back side is black, so it is possible to make the number of tiles with a white front side exactly $1$. Therefore output `Yes`. This sample input satisfies the constraints of subtasks $1,5,6,7$. ### Constraints - $1 \le N \le 300\,000$ - $S$ is a string of length $N$ consisting of `B` and `W` - $T$ is a string of length $N$ consisting of `B` and `W` - $1 \le Q \le 300\,000$ - $P_j$ is $1$ or $2$ ($1 \le j \le Q$) - If $P_j = 1$, then $1 \le X_j \le N$ ($1 \le j \le Q$) - If $P_j = 1$, then $Y_j$ is `'B'` or `'W'` ($1 \le j \le Q$) - If $P_j = 1$, then $Z_j$ is `'B'` or `'W'` ($1 \le j \le Q$) - If $P_j = 2$, then $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$) - If $P_j = 2$, then $0 \le M_j \le R_j - L_j + 1$ ($1 \le j \le Q$) - $N, Q, P_j, X_j, L_j, R_j, M_j$ are all integers. ### Subtasks 1. (6 points) $N \le 6$. 2. (10 points) $N \le 100$, and $P_j = 2$ ($1 \le j \le Q$). 3. (9 points) $N \le 500$, and $P_j = 2$ ($1 \le j \le Q$). 4. (8 points) $N \le 1700$, and $P_j = 2$ ($1 \le j \le Q$). 5. (23 points) $N \le 10\,000$, $Q \le 10\,000$. 6. (14 points) $N \le 100\,000$, $Q \le 100\,000$. 7. (30 points) No additional constraints. Translated by DeepSeek. Translated by ChatGPT 5