loj#P3520. 「JOI Open 2021」杂交

「JOI Open 2021」杂交

题目描述

译自 JOI Open 2021 T1 「交配 / Crossing

你知道「净是一些奇怪研究实验室」(Just Odd Investigations Laboratory)吗?这个实验室的业务就是去做「奇怪的研究」的。接下来我们简称其为 JOI 实验室。

最近几年,在世界各地的几个历史遗迹发现了盛开的大片花田。JOI 实验室发现花田中的花是新品种,并且它们的基因有相似的特征。这些新品种的花的基因是长度为 NN 且由 J, O, I\texttt{J, O, I} 组成的字符串。这些字符串被称为基因序列

你是在 JOI 实验室工作的研究院。你最初有三朵新品种的花。它们的基因序列分别为 SA,SB,SCS_A,S_B,S_C

你可以通过杂交的方式,让两朵新品种的花产生一种新品种的花。新得到的花的基因序列中第 ii 个字母按如下方式确定:

  • 如果两朵花的基因序列中第 ii 个字母是一样的,新得到的花的基因序列中第 ii 个字母将会和两亲本第 ii 个字母一致;
  • 如果两朵花的基因序列中第 ii 个字母是不一样的,新得到的花的基因序列中第 ii 个字母将会是 J, O, I\texttt{J, O, I} 中的一个,并和两亲本第 ii 个字母都不一样;

换句话说,如果两朵花基因序列的第 ii 个字母分别为 c1c_1c2c_2,新得到的花朵的基因序列中第 ii 个字母 c3c_3 如下表所示:

c1c_1 J\texttt J J\texttt J J\texttt J O\texttt O O\texttt O O\texttt O I\texttt I I\texttt I I\texttt I
c2c_2 J\texttt J O\texttt O I\texttt I J\texttt J O\texttt O I\texttt I J\texttt J O\texttt O I\texttt I
c3c_3 J\texttt J I\texttt I O\texttt O I\texttt I O\texttt O J\texttt J O\texttt O J\texttt J I\texttt I

你可以用相同的花朵杂交任意多次。如果你得到了一种新的花朵,你可以在随后的杂交中使用。

为了获得更多好看的花朵,JOI 实验室提出了 (Q+1)(Q+1) 个基因序列,它们从 00QQ 编号,并给了你一个描述这些候选基因序列的表。这个表包含一个字符串 T0T_0 和整数 Lj,RjL_j,R_j 和字符 CjC_j(这里 1jQ1\le j\le Q)。候选基因序列按如下规则给出。

  • 候选基因序列 00T0T_0
  • 候选基因序列 j (1jQ)j\ (1\le j\le Q) 是把候选基因序列 j1j-1 中从第 LjL_j 到第 RjR_j 个位置的字符全部替换为 CjC_j 得到的。

给定整数 NN 和初始三朵花的基因序列,描述候选基因序列的表,你需要写一个程序确定对于每一个候选基因序列,是否可以通过初始三朵花杂交零次及以上获得。

输入格式

第一行一个正整数 NN

接下来三行,每行一个长度为 NN 的字符串,分别为 SA,SB,SCS_A,S_B,S_C

接下来一行一个正整数 QQ

接下来一行一个长为 NN 的字符串 T0T_0

接下来 QQ 行,每行两个整数和一个字符 Lj,Rj,CjL_j,R_j,C_j

输出格式

输出 (Q+1)(Q+1) 行到标准输出。对于第 (j+1) (0jQ)(j+1)\ (0\le j\le Q) 行,如果可以通过通过初始三朵花杂交零次及以上获得候选基因序列 jj,则输出 Yes\texttt{Yes},否则输出 No\texttt{No}

4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

Yes
No
Yes
Yes

3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

No
No
Yes

数据范围与提示

对于全部数据,满足:

  • 1N2×1051\le N\le 2\times 10^5
  • SA,SB,SC,T0S_A,S_B,S_C,T_0 的长度均为 NN,并且只包含 J, O, I\texttt{J, O, I}
  • 1Q2×1051\le Q\le 2\times 10^5
  • 1LjRjN (1jQ)1\le L_j\le R_j\le N\ (1\le j\le Q)
  • Cj (1jQ)C_j\ (1\le j\le Q)J, O, I\texttt{J, O, I} 中的一个

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

子任务编号 附加限制 分值
11 SA=SB=SC,N100S_A=S_B=S_C,N\le 100 33
22 SA=SB=SCS_A=S_B=S_C 2323
33 N100N\le 100
44 无附加限制 5151