[AdditionalFile5606.zip](file://AdditionalFile5606.zip?type=additional_file)

#5606. 「JOI 2026 Semifinal」奇妙的机器

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Semifinal T6 「奇妙な機械 / Strange Machine」

你有 $N$ 块瓷砖，编号从 $1$ 到 $N$。每块瓷砖的正面和背面颜色要么是黑色，要么是白色。这里，黑色用字符 B 表示，白色用字符 W 表示。瓷砖 $i$ $(1 \leq i \leq N)$ 的正面颜色由字符串 $S$ 的第 $i$ 个字符表示，背面颜色由字符串 $T$ 的第 $i$ 个字符表示。

乌兹别克斯坦是一个以瓷砖装饰的历史建筑而闻名的国家。在访问了乌兹别克斯坦的清真寺和伊斯兰学校后，你被那些美丽的建筑所吸引，购买了一台关于瓷砖的奇妙机器。这台机器有左侧和右侧两个台座，如果在每个台座上各放一块瓷砖，作为交换，你可以用这两块瓷砖换取一块新的瓷砖。设放在左侧台座的瓷砖为 $a$，放在右侧台座的瓷砖为 $b$，作为交换得到的瓷砖 $c$ 满足以下条件：

• 如果 $a$ 的背面颜色和 $b$ 的正面颜色相同，$c$ 的正面颜色为黑色，否则为白色。
• 如果 $a$ 的正面颜色和 $b$ 的背面颜色相同，$c$ 的背面颜色为黑色，否则为白色。

你决定利用这 $N$ 块瓷砖和这台奇妙的机器，在 $Q$ 天内进行如下行动。第 $j$ $(1 \leq j \leq Q)$ 天进行的行动是以下两种模式之一：

• 模式 1：将瓷砖 $X_{j}$ 的正面颜色更改为字符 $Y_{j}$ 表示的颜色。同时，将瓷砖 $X_{j}$ 的背面颜色更改为字符 $Z_{j}$ 表示的颜色。其中，$Y_{j}, Z_{j}$ 均为 B 或 W。
• 模式 2：将瓷砖 $L_{j}, L_{j}+1, \ldots, R_{j}$ 按此顺序从左到右排成一列。对于这一列瓷砖，进行以下操作 $0$ 次或更多次（但不超过 $R_{j}-L_{j}$ 次），进行一次思想实验，判断是否能使列中正面颜色为白色的瓷砖恰好有 $M_{j}$ 块。
  • 在列中选择相邻的两块瓷砖并将它们从列中移除。将选中的两块瓷砖中原先位于左侧的放在机器的左侧台座，原先位于右侧的放在机器的右侧台座，用这两块瓷砖换取一块新瓷砖。然后，将换取的一块新瓷砖放入列中原先那两块瓷砖所在的位置。

给定瓷砖的信息和行动的信息，请编写程序求出模式 2 行动的结果。

输入格式

第一行包含一个整数 $N$。

第二行包含一个整数 $S$。

第三行包含一个整数 $T$。

第四行包含一个整数 $Q$。

接下来 $Q$ 行，每行描述了一个询问，包含若干空格分隔的整数。其中第一个是整数 $1$ 或 $2$，设其为 $P_{j}$，该行的内容如下：

• 当 $P_{j}=1$ 时，该行接着包含 $1$ 个整数 $X_{j}$ 和 $2$ 个字符 $Y_{j}, Z_{j}$，按此顺序排列。这表示你在第 $j$ 天采取的行动是模式 1，即将瓷砖 $X_{j}$ 的正面颜色更改为 $Y_{j}$，背面颜色更改为 $Z_{j}$。其中 $Y_{j}, Z_{j}$ 均为 B 或 W。
• 当 $P_{j}=2$ 时，该行接着包含 $3$ 个整数 $L_{j}, R_{j}, M_{j}$，按此顺序排列。这表示你在第 $j$ 天采取的行动是模式 2，即将瓷砖 $L_{j}, L_{j}+1, \ldots, R_{j}$ 按此顺序排列，并进行操作，判断是否能使列中正面颜色为白色的瓷砖恰好有 $M_{j}$ 块。

输出格式

对于每个 $P_{j}=2$ 的 $j$ $(1 \leq j \leq Q)$，如果能使列中正面颜色为白色的瓷砖恰好有 $M_{j}$ 块，则输出 Yes，否则输出 No，按 $j$ 从小到大换行输出。

样例 1

输入

4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1

输出

Yes
Yes
No
Yes

对于第 $1$ 天的行动，将瓷砖 $3, 4$ 按此顺序排成一列。如果不进行任何操作，只有瓷砖 $3$ 的正面是白色，因此可以使列中正面为白色的瓷砖恰好有 $1$ 块。输出 Yes。

对于第 $2$ 天的行动，将瓷砖 $1, 2$ 按此顺序排成一列。选择瓷砖 $1$ 和 $2$ 进行 $1$ 次操作，操作后的列包含 $1$ 块瓷砖。该瓷砖的正面和背面均为黑色，因此可以使列中正面为白色的瓷砖恰好有 $0$ 块。输出 Yes。

对于第 $3$ 天的行动，将瓷砖 $3$ 的正面和背面颜色都改为黑色。

对于第 $4$ 天的行动，将瓷砖 $3, 4$ 按此顺序排成一列。可以证明，无论如何操作，都无法使列中正面为白色的瓷砖恰好有 $2$ 块。输出 No。

对于第 $5$ 天的行动，将瓷砖 $2, 3, 4$ 按此顺序排成一列。选择瓷砖 $3$ 和 $4$ 进行 $1$ 次操作，操作后的列包含 $2$ 块瓷砖。左侧是瓷砖 $2$，右侧瓷砖的正面和背面均为黑色。再选择这两块瓷砖进行 $1$ 次操作，操作后的列包含 $1$ 块瓷砖。该瓷砖正面为白色，背面为黑色，因此可以使列中正面为白色的瓷砖恰好有 $1$ 块。输出 Yes。

此样例满足子任务 $1, 5, 6, 7$ 的限制。

样例 2

输入

6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2

输出

No
Yes
Yes
Yes
Yes
No
No
Yes

此样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 300000$
• $S$ 是由 B, W 组成的长度为 $N$ 的字符串。
• $T$ 是由 B, W 组成的长度为 $N$ 的字符串。
• $1 \leq Q \leq 300000$
• $P_{j}$ 是 $1$ 或 $2$ $(1 \leq j \leq Q)$
• 当 $P_{j}=1$ 时，$1 \leq X_{j} \leq N$ $(1 \leq j \leq Q)$
• 当 $P_{j}=1$ 时，$Y_{j}$ 是 B 或 W $(1 \leq j \leq Q)$
• 当 $P_{j}=1$ 时，$Z_{j}$ 是 B 或 W $(1 \leq j \leq Q)$
• 当 $P_{j}=2$ 时，$1 \leq L_{j} \leq R_{j} \leq N$ $(1 \leq j \leq Q)$
• 当 $P_{j}=2$ 时，$0 \leq M_{j} \leq R_{j}-L_{j}+1$ $(1 \leq j \leq Q)$
• $N, Q, P_{j}, X_{j}, L_{j}, R_{j}, M_{j}$ 均为整数。

详细子任务附加限制及分值如下表所示。