AT_joi2026_semifinal_f 奇妙な機械 (Strange Machine)

你有 $N$ 块编号从 $1$ 到 $N$ 的瓷砖。每块瓷砖的正面和反面颜色为黑色或白色。这里，黑色用字符 `B` 表示，白色用字符 `W` 表示。第 $i$ 块瓷砖（$1 \leq i \leq N$）的正面颜色由字符串 $S$ 的第 $i$ 个字符表示，其反面颜色由字符串 $T$ 的第 $i$ 个字符表示。 乌兹别克斯坦以其带有瓷砖装饰的历史建筑而闻名。你在参观清真寺与“马德拉萨”后，被美丽的建筑所吸引，并购买了一台奇特的机器。这台机器有左右两侧的台面，每次你可以在每个台面上各放置一块瓷砖，然后以这两块瓷砖为代价，获得一块新的瓷砖。假设放在左侧的是 $a$，右侧的是 $b$，那么交换后得到的新瓷砖 $c$ 满足： - $c$ 的正面颜色为：如果 $a$ 的反面颜色与 $b$ 的正面颜色相同，则为黑色，否则为白色。 - $c$ 的反面颜色为：如果 $a$ 的正面颜色与 $b$ 的反面颜色相同，则为黑色，否则为白色。 你将利用 $N$ 块瓷砖和这台奇怪的机器，在连续 $Q$ 天内按如下方式行动：第 $j$ 天（$1 \leq j \leq Q$）的行为有下述两种之一： - 模式 1：将第 $X_j$ 块瓷砖的正面颜色改为字符 $Y_j$，反面颜色改为字符 $Z_j$，其中 $Y_j, Z_j$ 为 `B` 或 `W`。 - 模式 2：将第 $L_j, L_j+1, \dots, R_j$ 块瓷砖按顺序从左到右排成一列。对于这一列，你可以进行 $0$ 次到 $R_j-L_j$ 次（任选次数）以下操作，思考能否使这列瓷砖中正面为白色的恰好为 $M_j$ 块： - 选择相邻的两块瓷砖，将其从列中移除。将左边那块放到机器左台面，右边那块放到右台面，用机器将这两块瓷砖换成一块新瓷砖，并将新瓷砖放回原两块的位置。 给定瓷砖信息及所有行为信息，请输出每个模式 2 的行为能否如要求达成，并按天数升序输出结果。 ---

输入由以下内容组成，通过标准输入读入： > $N$ $S$ $T$ $Q$ $(\text{Query }1)$ $(\text{Query }2)$ $\cdots$ $(\text{Query }Q)$ 每个 $(\text{Query }j)$（$1 \leq j \leq Q$）为一行，由若干整数和字符以空格分隔开，行首为整数 $1$ 或 $2$，记为 $P_j$，含义如下： - 当 $P_j = 1$，本行接着有整数 $X_j$ 和字符 $Y_j, Z_j$，表示第 $j$ 天采取模式 1，将第 $X_j$ 块瓷砖的正面、反面分别修改为 $Y_j, Z_j$（$Y_j, Z_j$ 均为 `B` 或 `W`）。 - 当 $P_j = 2$，本行后接整数 $L_j, R_j, M_j$，表示第 $j$ 天采取模式 2，将第 $L_j, L_j+1, \dots, R_j$ 块瓷砖排成一列，尝试通过规定的操作，使列中正面为白色的瓷砖恰好有 $M_j$ 块，进行可行性判定。

对于每个 $P_j = 2$ 的查询，若能够通过操作使得列中正面为白色的瓷砖数恰好为 $M_j$，输出 `Yes`，否则输出 `No`，每个结果占一行，按 $j$ 递增的顺序排列。 ---

### 子任务 1. （$6$ 分）$N \leq 6$。 2. （$10$ 分）$N \leq 100$，且 $P_j = 2 \ (1 \leq j \leq Q)$。 3. （$9$ 分）$N \leq 500$，且 $P_j = 2 \ (1 \leq j \leq Q)$。 4. （$8$ 分）$N \leq 1\,700$，且 $P_j = 2 \ (1 \leq j \leq Q)$。 5. （$23$ 分）$N \leq 10\,000$，$Q \leq 10\,000$。 6. （$14$ 分）$N \leq 100\,000$，$Q \leq 100\,000$。 7. （$30$ 分）无其他附加限制。 --- ### 样例解释 1 对于第 $1$ 天的操作，将第 $3,4$ 块瓷砖依次排列。不进行任何操作时，只有第 $3$ 块瓷砖的正面为白色，可以达成正面为白色的瓷砖数恰好为 $1$，因此输出 `Yes`。 对于第 $2$ 天的操作，将第 $1,2$ 块瓷砖依次排列。将第 $1,2$ 块瓷砖合成一次，合成后序列只剩一块，这块的正面与反面均为黑色，从而可以达到正面为白色的瓷砖数为 $0$，输出 `Yes`。 第 $3$ 天将第 $3$ 块瓷砖正反均改为黑色。 第 $4$ 天依次排列第 $3,4$ 块瓷砖。无法通过操作使正面为白色的瓷砖数变为 $2$，输出 `No`。 第 $5$ 天依次排列第 $2, 3, 4$ 块瓷砖。先合并第 $3,4$ 块，序列变为两块，左边是第 $2$ 块，右边是合成的块（正反均为黑色）。再将这两块瓷砖合成，最终得到一块瓷砖，正面为白色、反面为黑色，可以达成目标，输出 `Yes`。 本输入样例符合子任务 $1,5,6,7$ 的限制。 --- ### 样例解释 2 本输入样例满足所有子任务的限制。 ### 数据范围 - $1 \leq N \leq 300\,000$。 - $S$ 为长度 $N$ 且仅包含 `B`, `W` 的字符串。 - $T$ 为长度 $N$ 且仅包含 `B`, `W` 的字符串。 - $1 \leq Q \leq 300\,000$。 - $P_j$ 为 $1$ 或 $2$。 - 若 $P_j = 1$，$1 \leq X_j \leq N$。 - 若 $P_j = 1$，$Y_j$、$Z_j$ 为 `B` 或 `W`。 - 若 $P_j = 2$，$1 \leq L_j \leq R_j \leq N$。 - 若 $P_j = 2$，$0 \leq M_j \leq R_j - L_j + 1$。 - $N, Q, P_j, X_j, L_j, R_j, M_j$ 都是整数。 由 ChatGPT 5 翻译