Настя, как и вы — олимпиадный программист, но она только учится. Недавно Денис ей рассказал о способе проверки строки на то, что она является правильной скобочной последовательностью. После этого неожиданно Настя придумала более сложную задачу, которую Денис не смог решить, а сможете ли Вы?
Дана строка $$$s$$$, состоящая из $$$k$$$ видов пар скобок. Каждая скобка имеет вид $$$t$$$ — целое число, такое что $$$1 \leq |t| \leq k$$$. Если скобка имеет вид $$$t$$$, то:
Таким образом, всего существует $$$k$$$ типов пар скобок.
Требуется отвечать на следующие запросы:
Напомним определение правильной скобочной последовательности:
В первой строке дано $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — длина строки и число $$$k$$$ $$$(1 \leq k \leq n)$$$ — количество типов скобок.
Во второй строке дана строка $$$s$$$ длиной $$$n$$$ символов — $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \leq |s_i| \leq k)$$$.
В третьей строке дано число $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — количество запросов.
Каждая из следующих $$$q$$$ строк описывает запросы:
Для каждого запроса $$$2$$$ типа выведите «Yes», если подстрока из запроса является правильной скобочной последовательностью и «No», иначе.
Вы можете выводить буквы в любом регистре.
2 1 1 -1 1 2 1 2
Yes
2 2 1 -2 1 2 1 2
No
6 2 1 2 -2 -1 1 -1 3 2 1 6 2 1 4 2 2 5
Yes Yes No
2 2 -1 1 4 2 1 2 1 1 1 1 2 -1 2 1 2
No Yes
В четвёртом тесте изначально строка не является правильной скобочной последовательностью, значит ответ на первый вопрос «No». После двух изменений она имеет вид «$$$1$$$ $$$-1$$$», значит она стала правильной скобочной последовательностью и ответ на четвёртый запрос «Yes».
Название |
---|