分数: 600 点
问题陈述
让我们考虑对由以下内容组成的字符串进行以下操作 A 和 B:
- 选择字符串中的一个字符。如果是的话
A,替换为BB。如果是的话B,替换为AA. - 选择一个等于以下任一的子字符串
AAAorBBB,并将其从字符串中删除。
例如,如果第一个操作执行于 ABA 并选择第一个字符,字符串变为 BBBA。
如果执行第二次操作
选择 BBBAAAA 并选择第四到第六个字符,字符串变为 BBBA.
这些操作可以按任意顺序执行任意次数。
给你两个字符串 S 和 T,和 q 查询 a_i, b_i, c_i, d_i。 对于每个查询,确定是否 S_{a_i} S_{{a_i}+1} ... S_{b_i},一个子串 S,可以制成 T_{c_i} T_{{c_i}+1} ... T_{d_i},一个子串 T.
约束
- 1 \leq |S|, |T| \leq 10^5
- S 和 T 由字母组成
A和B. - 1 \leq q \leq 10^5
- 1 \leq a_i \leq b_i \leq |S|
- 1 \leq c_i \leq d_i \leq |T|
输入
输入由标准输入按以下格式给出:
S T q a_1 b_1 c_1 d_1 ... a_q b_q c_q d_q
输出
打印 q 行。的 i- 第行应包含对 i第一个查询。如果 S_{a_i} S_{{a_i}+1} ... S_{b_i} 可以制成 T_{c_i} T_{{c_i}+1} ... T_{d_i},打印 YES。否则,打印 NO.
示例输入 1
BBBAAAABA BBBBA 4 7 9 2 5 7 9 1 4 1 7 2 5 1 7 2 4
示例输出 1
YES NO YES NO
第一个查询询问字符串是否 ABA 可以制成 BBBA。
正如问题陈述中所解释的,可以通过第一个操作来完成。
第二个查询询问是否 ABA 可以制成 BBBB,第四个查询询问是否 BBBAAAA 可以制成 BBB。
两者都不可能。
第三个查询询问字符串是否 BBBAAAA 可以制成 BBBA。
正如问题陈述中所解释的,可以通过第二个操作来完成。
示例输入 2
AAAAABBBBAAABBBBAAAA BBBBAAABBBBBBAAAAABB 10 2 15 2 13 2 13 6 16 1 13 2 20 4 20 3 20 1 18 9 19 2 14 1 11 3 20 3 15 6 16 1 17 4 18 8 20 7 20 3 14
示例输出 2
YES YES YES YES YES YES NO NO NO NO