配点: 100 点
問題文
你是瓷砖
来自 1 的瓷砖
编号至 N 您有 N 块。每块瓷砖的正面和背面颜色都是黑色或白色。这里,黑色是字符 B ,白色是字符
让我们将其表示为 W 。
瓷砖 i (1 \leqq i \leqq N) 的表面颜色是字符串 S 可以得到第 i 这是字母代表的颜色。
瓷砖 i (1 \leqq i \leqq N) 的背面颜色是字符串 T 可以得到第 i 这是字母代表的颜色。
乌兹别克斯坦是一个以瓷砖装饰的历史建筑而闻名的国家。您参观了乌兹别克斯坦的清真寺和宗教学校,对它们美丽的建筑非常着迷,以至于您购买了一台奇怪的瓷砖机。本机左右两侧各有一个支架,每个支架上有 1 通过一张一张地放置瓷砖, 用 2 方块换取新方块。 您可以获得 1 件。 放置在左侧支架上的图块 a、放置在右侧支架上的图块 当 b 时, 我想知道,“有多少种方法可以选择一个整数使得2 瓷砖 可以用 a, b 交换获得的新瓷砖 c 满足以下条件。
- c 表面的颜色是a 背面的颜色 b 表面颜色相同时为黑色;否则,它是白色的。
- c 背面的颜色是a 表面颜色和 如果 b 的背面颜色相同,则为黑色;否则,它是白色的。
你 N 瓷砖和一台奇怪的机器,Q 我决定在接下来的几天内执行以下操作。j 日目 (1 \leqq j \leqq 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 图块并将其从列中删除。选择了 2 在瓷砖中,将放置在该行左侧的瓷砖放置在机器的左侧,将放置在右侧的瓷砖放置在机器的右侧。 2 方块换取新方块。原来在专栏里 在有 2 瓷砖的地方, 插入 1 方块。
给定图块信息和行为信息,模式 编写一个程序来查找 2 操作的结果。
入力
输入是按以下格式从标准输入给出的。
N
S
T
Q
(\text{Query }1)
(\text{Query }2)
\vdots
(\text{Query }Q)
各 (\text{Query }j) (1 \leqq j \leqq Q) 包含多个以空格分隔的整数和字符。第一个写入的是一个整数 1, 2 ,这是 P_j 该行的内容是以下内容之一。
- P_j = 1 ,此行后面是 1 整数
给出了 X_j 和
按字典顺序比较 2 字符
假设 Y_j, Z_j 按此顺序写入。这就是你 j 你每天的行为是一种模式 1 和瓷砖
将颜色更改为 X_j 表面颜色作为文本
将颜色更改为 Y_j 并平铺
表示更改为 X_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, \dots, R_j 按照从左到右的顺序排成一行,对该行进行操作,并精确选择该行中表面为白色的瓷砖。 M_j 它代表进行思想实验以确定是否有可能
出力
P_j = 2 变为 j (1 \leqq j \leqq Q) 对于每个,请准确选择列中的白面瓷砖。
当可以制作 M_j 件时 Yes ,否则 No ,j ,并以换行符分隔。
长度由
制約
- 1 \leqq N \leqq 300\,000.
- S 是
您也可以写
B,W组成的长度 N 的字符串. - T 是
您也可以写
B,W组成的长度 N 的字符串. - 1 \leqq Q \leqq 300\,000.
- P_j 是 您也可以写 1,2 (1 \leqq j \leqq Q).
- P_j = 1 时,1 \leqq X_j \leqq N (1 \leqq j \leqq Q).
- P_j = 1 时,Y_j 是
您也可以写
B,W(1 \leqq j \leqq Q). - P_j = 1 时,Z_j 是
您也可以写
B,W(1 \leqq j \leqq Q). - P_j = 2 时,1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q).
- P_j = 2 时,0 \leqq M_j \leqq R_j - L_j + 1 (1 \leqq j \leqq Q).
- N, Q, P_j, X_j, L_j, R_j, M_j 均为整数。
小課題
- (6 点) N \leqq 6.
- (10 点) N \leqq 100,P_j = 2 (1 \leqq j \leqq Q).
- (9 点) N \leqq 500,P_j = 2 (1 \leqq j \leqq Q).
- (8 点) N \leqq 1\,700,P_j = 2 (1 \leqq j \leqq Q).
- (23 点) N \leqq 10\,000,Q \leqq 10\,000.
- (14 点) N \leqq 100\,000,Q \leqq 100\,000.
- (30 点)没有额外的限制。
入力例 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
出力例 1
Yes Yes No Yes
1 关于当天的行动,瓷砖
按从左到右的顺序排列 3, 4 。操作 1 如果您根本不执行此操作,则图块 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 ,右侧图块的正面和背面均为黑色。这个
选择 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
出力例 2
No Yes Yes Yes Yes No No Yes
此输入示例满足所有子任务约束。