Codeforces Round 878 (Div. 3) |
---|
Закончено |
Дано две строки равной длины $$$s_1$$$ и $$$s_2$$$, состоящие из строчных букв латинского алфавита, и натуральное число $$$t$$$.
Вам необходимо ответить на $$$q$$$ запросов, пронумерованных от $$$1$$$ до $$$q$$$. $$$i$$$-й запрос приходит в $$$i$$$-ю секунду времени. Каждый запрос одного из трёх типов:
Заметьте, в запросах второго типа местами могут менять как символы, принадлежащие одной строке, так и символ из $$$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$$$ строк набора содержатся сами запросы — по одному в строке. Каждый запрос одного из трёх типов:
Для запросов первого типа гарантируется, что на момент запроса символы на позиции $$$pos$$$ не заблокированы.
Для запросов второго типа гарантируется, что меняющиеся местами символы не заблокированы.
Все значения $$$pos, pos_1, pos_2$$$ лежат в диапазоне от $$$1$$$ до длин строк.
Сумма значений $$$q$$$ по всем наборам входных данных, а также суммарная длина строк $$$s_1$$$ не превосходит $$$2 \cdot 10^5$$$.
Для каждого запроса третьего типа выведите «YES», если на момент запроса строки $$$s_1$$$ и $$$s_2$$$ равны без учёта заблокированных символов, «NO» — иначе.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
2codeforcescodeblocks5 731 51 61 71 933coolclub2 52 1 2 2 32 2 2 2 41 233
NO YES NO YES NO
Давайте посмотрим на строки $$$s_1$$$ и $$$s_2$$$ после каждого из $$$q$$$ запросов. Будем обозначать красным цветом заблокированные символы.
Первый пример входных данных:
($$$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$$$)
Название |
---|