← 返回题目列表

Codeforces · 1840/E

E. 字符阻塞

中文机器翻译题面 查看原题

给定两个长度相等的字符串 $$$s_1$$$ 和 $$$s_2$$$(由小写拉丁字母组成)和一个整数 $$$t$$$。

您需要回答 $$$q$$$ 查询,编号从 $$$1$$$ 到 $$$q$$$。第 $$$i$$$ 查询出现在第 $$$i$$$ 秒内。每个查询都是以下三种类型之一:

- 阻止两个字符串中位置 $$$pos$$$(从 $$$1$$$ 索引)处的字符 $$$t$$$ 秒;
- 交换两个未阻塞的字符;
- 确定查询时两个字符串是否相等,忽略阻塞字符。

请注意,在第二种类型的查询中,被交换的字符可以来自同一字符串,也可以来自 $$$s_1$$$ 和 $$$s_2$$$。

输入

输入的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$) — 测试用例的数量。

然后按照测试用例的描述进行操作。

每个测试用例的第一行包含一个由小写拉丁字母组成的字符串$$$s_1$$$(长度不超过$$$2 \cdot 10^5$$$)。

每个测试用例的第二行包含一个由小写拉丁字母组成的字符串$$$s_2$$$(长度不超过$$$2 \cdot 10^5$$$)。

字符串长度相等。

每个测试用例的第三行包含两个整数 $$$t$$$ 和 $$$q$$$ ($$$1 \le t, q \le 2 \cdot 10^5$$$)。数字 $$$t$$$ 表示字符被阻止的秒数。数字 $$$q$$$ 对应于查询的数量。

每个测试用例的接下来的 $$$q$$$ 行都包含一个查询。每个查询都是以下三种类型之一:

- "$$$1\ \ \ pos$$$" — 阻止两个字符串中 $$$pos$$$ 位置处的字符 $$$t$$$ 秒;
- "$$$2\ \ \ 1/\;\!2\ \ \ pos_1\ \ \ 1/\;\!2\ \ \ pos_2$$$" — 交换两个未阻止的字符。查询中的第二个数字表示从中获取交换的第一个字符的字符串的编号。查询中的第三个数字表示该字符在该字符串中的位置。查询中的第四个数字表示从中获取用于交换的第二个字符的字符串的编号。查询中的第五个数字表示该字符在该字符串中的位置;
- "$$$3$$$" — 确定查询时两个字符串是否相等,忽略被阻止的字符。

对于第一类查询,保证查询时$$$pos$$$位置的字符不被遮挡。

对于第二种类型的查询,保证正在交换的字符不被阻塞。

$$$pos、pos_1、pos_2$$$ 的所有值都在从 $$$1$$$ 到字符串长度的范围内。

所有测试用例的 $$$q$$$ 值的总和以及字符串 $$$s_1$$$ 的总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于第三种类型的每个查询,如果查询时两个字符串 $$$s_1$$$ 和 $$$s_2$$$ 相等,则输出“YES”,忽略阻塞字符,否则输出“NO”。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

示例

输入 #1

2
codeforces
codeblocks
5 7
3
1 5
1 6
1 7
1 9
3
3
cool
club
2 5
2 1 2 2 3
2 2 2 2 4
1 2
3
3

输出 #1

NO
YES
NO
YES
NO

注意

让我们看看每个 $$$q$$$ 查询之后的字符串 $$$s_1$$$ 和 $$$s_2$$$。被阻止的字符将以红色表示。

第一个示例输入:

($$$codeforces$$$, $$$codeblocks$$$) $$$\rightarrow$$$ ($$$codeforces$$$, $$$codeblocks$$$) $$$\rightarrow$$$ ($$$code\color{red}{f}orces$$$, $$$code\color{red}{b}locks$$$) $$$\rightarrow$$$ ($$$code\color{red}{fo}rces$$$, $$$code\color{red}{bl}ocks$$$) $$$\rightarrow$$$ ($$$code\color{red}{for}ces$$$, $$$code\color{red}{blo}cks$$$) $$$\rightarrow$$$ ($$$code\color{red}{for}c\color{red}{e}s$$$, $$$code\color{red}{blo}c\color{red}{k}s$$$) $$$\rightarrow$$$ ($$$code\color{red}{for}c\color{red}{e}s$$$, $$$code\color{red}{blo}c\color{red}{k}s$$$) $$$\rightarrow$$$ ($$$codef\color{red}{or}c\color{red}{e}s$$$, $$$codeb\color{red}{lo}c\color{red}{k}s$$$)

第二个示例输入:

($$$cool$$$, $$$club$$$) $$$\rightarrow$$$ ($$$cuol$$$, $$$clob$$$) $$$\rightarrow$$$ ($$$cuol$$$, $$$cbol$$$) $$$\rightarrow$$$ ($$$c\color{red}{u}ol$$$, $$$c\color{red}{b}ol$$$) $$$\rightarrow$$$ ($$$c\color{red}{u}ol$$$, $$$c\color{red}{b}ol$$$) $$$\rightarrow$$$ ($$$cuol$$$, $$$cbol$$$)