Codeforces Round 877 (Div. 2) |
---|
Закончено |
Дана строка $$$s$$$ длины $$$n$$$, состоящая из символов '(' и ')'. Вы идете по этой строке. Вы начинаете с первого символа $$$s$$$ и хотите сделать последовательность шагов так, чтобы закончить на $$$n$$$-м символе. За один шаг вы можете переместиться на один символ влево (если вы стоите не на первом символе) или на один символ вправо (если вы стоите не на последнем символе). Вы не можете оставаться на одном и том же месте, однако вы можете посетить любой символ, включая первый и последний, любое количество раз.
В каждый момент времени вы записываете символ, на котором вы сейчас стоите. Мы говорим, что строка проходима, если существует некоторая последовательность ходов, начинающаяся в первом символе и заканчивающаяся в последнем, такая, что записанная вами строка является правильной скобочной последовательностью.
Правильная скобочная последовательность — это последовательность скобок, которая может быть преобразована в правильное арифметическое выражение путем добавления символов '1' и '+' между исходными символами последовательности. Например, последовательности скобок «()()», «(())» являются правильными ( итоговыми выражениями являются: «(1)+(1)», «((1+1)+1)»), а последовательности «)(» и «(» не являются правильными.
Вам даны $$$q$$$ запросов. Каждый запрос меняет значение символа с '(' на ')' или наоборот. После каждого изменения определите, является ли данная строка проходимой.
Запросы сохраняются, то есть эффект от каждого запроса распространяется на последующие запросы.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) — размер строки и количество запросов, соответственно.
Вторая строка ввода содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов '(' и ')' — начальная строка.
Каждая из следующих $$$q$$$ строк содержит одно целое число $$$i$$$ ($$$1\le i \le n$$$) — индекс символа, который нужно изменить в данном запросе.
Для каждого запроса выведите «YES», если строка проходима после этого запроса, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «YEs», «Yes», «Yes» и «YES» будут распознаны как положительные ответы.
10 9 (())()())) 9 7 2 6 3 6 7 4 8
YES YES NO NO YES NO YES NO NO
3 2 (() 2 3
NO NO
В первом примере:
Название |
---|