410172: GYM103967 H Портальная пушка
Description
Рик прекрасно знает, что Морти нельзя доверять портальную пушку, но в последнее время Морти так надоел ему просьбами подарить ему собственную портальную пушку, что Рик сдался и сделал ему мини-версию.
Однако, чтобы Морти при этом как-то развивался (или просто чтобы ему было сложнее ее использовать), Рик сделал ее устройство достаточно запутанным. Всего на портальной пушке Морти есть $$$n$$$ параметров, каждый из которых может принимать значения от 'a' до 'z'. Обозначим параметр под номером $$$i$$$ за $$$p_i$$$.
За одно действие Морти может:
- выбрать произвольный номер параметра $$$i$$$ от $$$1$$$ до $$$n$$$ и изменить его значение на произвольное другое $$$c$$$ от 'a' до 'z';
- выбрать два возможных значения $$$c_1$$$ и $$$c_2$$$ от 'a' до 'z' и заменить значение у всех параметров, текущее значение которых равно $$$c_1$$$, на $$$c_2$$$;
- проверить, можно ли создать порталы в локациях с идентификаторами $$$(l_1, r_1)$$$ и $$$(l_2, r_2)$$$ (где $$$l_1 \leqslant r_1$$$ и $$$l_2 \leqslant r_2$$$) — для этого набор параметров на позициях $$$[l_1, r_1]$$$ должен поэлементно совпадать с набором параметров на позициях $$$[l_2, r_2]$$$, то есть должно выполняться $$$$$$\begin{cases} r_1 - l_1 = r_2 - l_2 \\ p_{l_1 + i} = p_{l_2 + i} & \text{для всех } 0 \leqslant i \leqslant r_1 - l_1 \end{cases}\text{.}$$$$$$
Поскольку Морти не шибко умный, ему сложно быстро проверять наборы параметров на равенство, а случайно сломать портальную пушку не хотелось бы. Помогите ему для каждого действия третьего типа понять, может ли он создать порталы в желаемых локациях, или нет.
Входные данныеВ первой строке ввода дана строка $$$p$$$ длины $$$n$$$, состоящая из маленьких латинских букв — изначальные значения параметров пушки ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$).
В следующей строке дано единственное целое число $$$q$$$ — количество действий, которые совершает Морти ($$$1 \leqslant q \leqslant 2 \cdot 10^5$$$).
В следующих $$$q$$$ строках перечислены описания действий:
- «1 $$$i$$$ $$$c$$$» — присвоить $$$i$$$-му параметру значение $$$c$$$ ($$$1 \leqslant i \leqslant n$$$; $$$\text{'\t{a}'} \leqslant c \leqslant \text{'\t{z}'}$$$);
- «2 $$$c_1$$$ $$$c_2$$$» — заменить все значения всех параметров, равных $$$c_1$$$, на $$$c_2$$$ ($$$\text{'\t{a}'} \leqslant c_1, c_2 \leqslant \text{'\t{z}'}$$$);
- «3 $$$l_1$$$ $$$r_1$$$ $$$l_2$$$ $$$r_2$$$» — проверить возможность создания порталов в локациях $$$(l_1, r_1)$$$ и $$$(l_2, r_2)$$$ ($$$1 \leqslant l_1, r_1, l_2, r_2 \leqslant n$$$; $$$l_1 \leqslant r_1$$$; $$$l_2 \leqslant r_2$$$).
На каждое действие третьего типа выведите в отдельной строке «YES» (без кавычек), если Морти может его выполнить, и «NO» иначе.
ПримерыВходные данныеaaabc 6 3 1 2 2 3 1 4 c 2 c a 3 1 4 2 5 1 3 x 3 1 4 2 5Выходные данные
YES YES NOВходные данные
abracadabra 7 3 1 4 8 11 1 7 r 2 a c 2 b c 3 1 4 8 11 3 1 4 5 8 3 2 4 6 8Выходные данные
YES YES YES YES