1255: MC 基因工程
题目
题目描述
你知道 MC 基因工程吗？
近年来，我们惊奇的发现，在 MC 的世界中，同样有着和现实世界类似的基因的遗传现象。在这里，所有生物的遗传信息都可以由长度为 $N$ 的，仅包含字母 X, Y, Z 的字符串来描述。
现在，你参与了 MC 基因工程。刚开始，你只有三种不同种类的花，它们的基因序列可以被看做长度为 $N$ 的字符串 $S_A, S_B, S_C$。你可以通过对两种花进行杂交操作，得到拥有新的性状的花朵。规则如下：
- 在亲代中，第 $i(1\leq i \leq N)$ 个字符代表的基因片段相同，那么它们杂交之后得到的子代的第 $i$ 个性状将会和亲代一摸一样。
- 在亲代中，第 $i(1\leq i \leq N)$ 个字符代表的基因片段不同，那么它们杂交之后得到的子代的第 $i$ 个性状将会和任一个亲代的改基因片段都不同。
形象地说，如果亲代中的第 $i$ 个字符分别为 $c_1$ 和 $c_2$，那么子代性状 $c_3$ 满足以下表格。
```text c1 | X X X Y Y Y Z Z Z c2 | X Y Z X Y Z X Y Z
c3 | X Z Y Z Y X Y X Z ```
注意：花朵之间可以任意杂交，杂交后代可以用于重复杂交。
为了培育出更多好看的花朵，MC 基因工程计算出了 $Q+1$ 种候选的基因序列 $T_0 \sim T_Q$。其中：
- $T_0$ 序列是一个长度为 $N$ 的直接给出的字符串
- $T_i$ 序列 $(1\leq i \leq Q)$ 可以由 $T_{i-1}$ 序列将 $L_i$ 到 $R_i$ 位的基因全部修改为 $C_i$ 得到。
编写一段程序，给定三种初始花朵的基因序列，以及 $Q+1$ 个候选基因序列，你需要判断出每一种基因序列是否可以通过有限次杂交得到。
输入格式
第一行的输入一个整数 $N$，代表基因序列的长度
第二行输入一个字符串 $S_A$
第三行输入一个字符串 $S_B$
第四行输入一个字符串 $S_C$
第五行的输入一个整数 $Q$
第六行输入一个字符串 $T_0$
接下来的 $Q$ 行，每行输入 $L_i, R_i, C_i$，中间用空格隔开
输出格式
输出 $Q+1$ 行，依次代表每一个候选基因序列是否能够通过给定的三个初始基因序列 $S_A, S_B, S_C$ 经过有限次杂交得到。如果可以，那么输出 Yes，不然就输出 No
样例输入
样例输入 1
text
4
XYXY
XXYZ
YXYY
3
ZXYX
1 4 Y
2 2 X
2 4 Z
T0 = ZXYX，可以通过XXYZ和YXYY杂交得来T1 = YYYY，无法杂交获得T2 = YXYY，我们本来就有这个T3 = YZZZ，我们先通过XXYZ和YXYY杂交得到ZXYX，然后继续通过ZXYX和XYXY杂交，就可以得到
样例输入 2
text
3
XYZ
XYZ
XYZ
2
YXZ
1 2 Y
1 1 X
T0 = YXZT1 = YYZT2 = XYZ
样例输出
样例输出 1
text
Yes
No
Yes
Yes
样例输出 2
text
No
No
Yes
数据范围
时间限制：3000 ms 空间限制：512 mb
全局限制
- $1\leq N, Q \leq 2\times 10^5$
- $S_A, S_B, S_C, T_0$ 都是长度为 $N$，且仅包含
X,Y,Z的字符串 - $1\leq L_i\leq R_i\leq N$
- $C_i$ 是字符
X或者Y或者Z
部分限制
- $(\text{10 points})~S_A = S_B = S_C, N\leq 100$
- $(\text{30 points})~S_A = S_B = S_C$
- $(\text{30 points})~N\leq 100$
- $(\text{30 points})$ 无限制
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！