Character Blocking_信奥算法普及/提高--ACGO题库

题目描述

You are given two strings of equal length $s_1$ and $s_2$ , consisting of lowercase Latin letters, and an integer $t$ .

You need to answer $q$ queries, numbered from $1$ to $q$ . The $i$ -th query comes in the $i$ -th second of time. Each query is one of three types:

block the characters at position $pos$ (indexed from $1$ ) in both strings for $t$ seconds;
swap two unblocked characters;
determine if the two strings are equal at the time of the query, ignoring blocked characters.

Note that in queries of the second type, the characters being swapped can be from the same string or from $s_1$ and $s_2$ .

给你两个等长的字符串 $s_1$ 和 $s_2$ ，均由小写拉丁字母组成，以及一个整数 $t$ 。

你需要回答 $q$ 个查询，查询编号从 $1$ 到 $q$ 。第 $i$ 个查询发生在第 $i$ 秒。每个查询为以下三种类型之一：

将两个字符串中位置 $pos$ （下标从 $1$ 开始）处的字符封锁 $t$ 秒；
交换两个未被封锁的字符；
判断在该查询时刻，忽略所有被封锁的字符后，两个字符串是否相等。

注意：对于第二种类型的查询，被交换的字符可以来自同一字符串，也可以分别来自 $s_1$ 和 $s_2$ 。

输入格式

The first line of the input contains a single integer $T$ ( $1 \le T \le 10^4$ ) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains a string $s_1$ consisting of lowercase Latin letters (length no more than $2 \cdot 10^5$ ).

The second line of each test case contains a string $s_2$ consisting of lowercase Latin letters (length no more than $2 \cdot 10^5$ ).

The strings have equal length.

The third line of each test case contains two integers $t$ and $q$ ( $1 \le t, q \le 2 \cdot 10^5$ ). The number $t$ indicates the number of seconds for which a character is blocked. The number $q$ corresponds to the number of queries.

Each of the next $q$ lines of each test case contains a single query. Each query is one of three types:

" $1\ \ \ pos$ " — block the characters at position $pos$ in both strings for $t$ seconds;
" $2\ \ \ 1/\;\!2\ \ \ pos_1\ \ \ 1/\;\!2\ \ \ pos_2$ " — swap two unblocked characters. The second number in the query indicates the number of the string from which the first character for the swap is taken. The third number in the query indicates the position in that string of that character. The fourth number in the query indicates the number of the string from which the second character for the swap is taken. The fifth number in the query indicates the position in that string of that character;
" $3$ " — determine if the two strings are equal at the time of the query, ignoring blocked characters.

For queries of the first type, it is guaranteed that at the time of the query, the characters at position $pos$ are not blocked.

For queries of the second type, it is guaranteed that the characters being swapped are not blocked.

All values of $pos, pos_1, pos_2$ are in the range from $1$ to the length of the strings.

The sum of the values of $q$ over all test cases, as well as the total length of the strings $s_1$ , does not exceed $2 \cdot 10^5$ .

输入的第一行包含一个整数 $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$ ” —— 交换两个未被封锁的字符。查询中的第二个数表示第一个待交换字符所在字符串的编号（ $1$ 或 $2$ ）；第三个数表示该字符在对应字符串中的位置；第四个数表示第二个待交换字符所在字符串的编号（ $1$ 或 $2$ ）；第五个数表示该字符在对应字符串中的位置；
“ $3$ ” —— 判断在当前时刻，忽略所有被封锁的字符后，两个字符串是否相等。

对于第一类查询，保证在查询发生时，位置 $pos$ 上的字符尚未被封锁。

对于第二类查询，保证待交换的两个字符均未被封锁。

所有 $pos$ 、 $pos_1$ 、 $pos_2$ 的取值范围均为 $1$ 到字符串长度（含端点）。

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

输出格式

For each query of the third type, output "YES" if the two strings $s_1$ and $s_2$ are equal at the time of the query, ignoring blocked characters, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes" and "YES" will be accepted as a positive answer.

对于每个第三种类型的查询，在查询时刻，若忽略被屏蔽的字符后两个字符串 $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

说明/提示

Let's look at the strings $s_1$ and $s_2$ after each of the $q$ queries. Blocked characters will be denoted in red.

First example input:

( $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$ )

Second example input:

( $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$ )

我们来观察每次执行 $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$ )