P15456 [JOI 2026 SemiFinal] 奇妙的机器 / Strange Machine

你拥有 $N$ 枚瓷砖，编号为 $1$ 到 $N$。每枚瓷砖的正面和反面颜色均为黑色或白色。这里，黑色用字符 `'B'` 表示，白色用字符 `'W'` 表示。瓷砖 $i$（$1 \le i \le N$）的正面颜色由字符串 $S$ 的第 $i$ 个字符表示，瓷砖 $i$ 的反面颜色由字符串 $T$ 的第 $i$ 个字符表示。 乌兹别克斯坦以其瓷砖装饰的历史建筑而闻名。在参观了乌兹别克斯坦的清真寺和伊斯兰学校后，你被这些美丽的建筑所吸引，并购买了一台奇特的机器。这台机器左右两侧各有一个平台，在每个平台上各放置一枚瓷砖，就可以用这两枚瓷砖换得一枚新瓷砖。设左平台放置的瓷砖为 $a$，右平台放置的瓷砖为 $b$，则用 $a$ 和 $b$ 换得的新瓷砖 $c$ 满足以下条件： - $c$ 的正面颜色：若 $a$ 的反面颜色与 $b$ 的正面颜色相同则为黑色，否则为白色。 - $c$ 的反面颜色：若 $a$ 的正面颜色与 $b$ 的反面颜色相同则为黑色，否则为白色。 你打算用这 $N$ 枚瓷砖和这台奇特机器，在 $Q$ 天里进行以下活动。第 $j$ 天（$1 \le j \le Q$）的活动为模式 1 或模式 2 之一： - **模式 1**：将瓷砖 $X_j$ 的正面颜色改为字符 $Y_j$ 所表示的颜色，并将瓷砖 $X_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$ (Query 1) (Query 2) $\vdots$ (Query $Q$) 每个 (Query $j$)（$1 \le j \le 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$ 的 $j$（$1 \le j \le Q$），按 $j$ 的升序每行输出一个结果：如果能使该列中正面为白色的瓷砖恰好为 $M_j$ 枚，则输出 `Yes`，否则输出 `No`。

#### 样例解释 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$，右侧为新瓷砖（其正面和反面均为黑色）。再选择这两枚瓷砖进行一次操作，操作后列中剩一枚瓷砖，其正面为白色、反面为黑色，因此可以使正面为白色的瓷砖恰好为 $1$ 枚。故输出 `Yes`。 该输入样例满足子任务 $1,5,6,7$ 的数据范围。 ### 数据范围 - $1 \le N \le 300\,000$ - $S$ 是由 `B`、`W` 组成的长度为 $N$ 的字符串 - $T$ 是由 `B`、`W` 组成的长度为 $N$ 的字符串 - $1 \le Q \le 300\,000$ - $P_j$ 为 $1$ 或 $2$（$1 \le j \le Q$） - 当 $P_j = 1$ 时，$1 \le X_j \le N$（$1 \le j \le Q$） - 当 $P_j = 1$ 时，$Y_j$ 为 `'B'` 或 `'W'`（$1 \le j \le Q$） - 当 $P_j = 1$ 时，$Z_j$ 为 `'B'` 或 `'W'`（$1 \le j \le Q$） - 当 $P_j = 2$ 时，$1 \le L_j \le R_j \le N$（$1 \le j \le Q$） - 当 $P_j = 2$ 时，$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$ 均为整数 ### 子任务 1. (6 分) $N \le 6$ 2. (10 分) $N \le 100$，且 $P_j = 2$（$1 \le j \le Q$） 3. (9 分) $N \le 500$，且 $P_j = 2$（$1 \le j \le Q$） 4. (8 分) $N \le 1700$，且 $P_j = 2$（$1 \le j \le Q$） 5. (23 分) $N \le 10\,000$，$Q \le 10\,000$ 6. (14 分) $N \le 100\,000$，$Q \le 100\,000$ 7. (30 分) 无额外限制 翻译由 DeepSeek 完成