Задача №114974. Австралийская ПСП
Как известно, в Австралии смотрят на вещи под самыми разными углами, поэтому и правильные скобочные последовательности они задают нестандартным способом:
- Пустая скобочная последовательность считается правильной.
- Если \(S\) считается правильной, то ) \(S\) ( , ( \(S\) ) , [ \(S\) ] , ] \(S\) [ , { \(S\) } , } \(S\) { , < \(S\) > и > \(S\) < тоже считаются правильными.
- Если \(S\) и \(T\) считаются правильными, то \(S + T\) тоже считается правильной (здесь \(+\) означает конкатенацию строк).
Мальчик Вася решил посетить Австралию. Но вот беда, для этого надо пройти австралийский тест на интеллект! В самом сложном задании теста даётся строка \(s\), состоящая из скобок и к ней даются \(m\) заданий двух видов:
- Заменить скобку на позиции \(a_i\).
- Сказать, считается ли подстрока \(s\) на позициях с \(l_i\) по позицию \(r_i\) включительно правильной скобочной последовательностью в Австралии.
Вася очень просит вас помочь ему пройти тест.
Первая строка содержит единственное целое число \(n\) (\(1 \le n \le 200\,000\)) — длину скобочной последовательности.
Во второй строке содержится строка \(s\) длины \(n\), состоящая из скобок ()[]{}<> — исходная строка, данная Васе.
В третьей строке содержится целое число \(m\) (\(1 \le m \le 200\,000\)) — количество заданий теста.
В следующих \(m\) строках заданы запросы. В \(i\)-й из следующих строк в начале содержится целое число \(t_i\) (\(1 \le t_i \le 2\)).
- Если \(t_i = 1\), то далее строка содержит целое число \(a_i\) и символ \(c_i\) (\(1 \le a_i \le n\)). В этом случае требуется в строке \(s\) на позиции \(a_i\) заменить скобку на \(c_i\). Гарантируется, что \(c_i\) является одной из скобок ()[]{}<> .
- Если \(t_i = 2\), то далее строка содержит два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)). В этом случае требуется узнать, считается ли подстрока \(s\) на позициях с \(l_i\) по позицию \(r_i\) правильной скобочной последовательностью в Австралии.
Для каждого запроса второго типа выведите « Yes » (без кавычек), если скобочная последовательность считается правильной и « No » (без кавычек) иначе.
В первом примере:
- В первом задании просят сказать, считается ли подстрока « )()(() » правильной. Ответ « Yes », так как « )( » и « () » считаются правильными, а эта подстрока представляется, как сумма таких строк.
- Во втором задании просят заменить скобку на \(4\)-й позиции на ) . После этого строка будет равна « )())() ».
- В третьем задании просят сказать, считается ли подстрока « ())( » правильной. Ответ « Yes » аналогично первому заданию.
- В четвёртом задании просят заменить скобку на \(3\)-й позиции на [ . После этого строка будет равна « )([)() ».
- В пятом задании просят заменить скобку на \(4\)-й позиции на ] . После этого строка будет равна « )([]() ».
- В шестом задании просят сказать, считается ли подстрока « )([]() » правильной. Ответ « Yes » аналогично предыдущим заданиям, так как « [] » тоже считается правильной.
- В седьмом задании просят сказать, считается ли подстрока « ]( » правильной. Но нетрудно убедиться, что правильной она не считается, поэтому ответ « No ».
Во втором примере:
- В первом задании просят сказать, считается ли подстрока « >())(][<}{ » правильной. Ответ « Yes », так как « () » и « )( » считаются правильными, поэтому их сумма « ())( » считается правильной, поэтому строка « >())(< » считается правильной. Также « }{ » считается правильной, поэтому исходная подстрока считается правильной.
- Во втором задании просят заменить скобку на \(3\)-й позиции на ( . После этого строка будет равна « >(()(][<}{ ».
- В третьем задании просят сказать, считается ли подстрока « >(()(][<}{ » правильной. Ответ « No », так как иначе строка « (()( » считалась бы правильной, но нетрудно убедиться, что это не так.
- В четвёртом задании просят сказать, считается ли подстрока « (()( » правильной. Нетрудно убедиться, что правильной она не считается, поэтому ответ « No »
- В пятом задании просят заменить скобку на \(2\)-й позиции на ) . После этого строка будет равна « >)()(][<}{ ».
- В шестом задании просят сказать, считается ли подстрока « >)()(][<}{ » правильной. Ответ « Yes », так как « )()( » правильная, поэтому и « >)()(< » правильная, поэтому и исходная подстрока правильная.
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(t_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 16 | \(n \le 100\) | \(m \le 100\) | – | 0 | |
| 2 | 15 | \(n \le 10\,000\) | \(m \le 10\,000\) | – | 0, 1 | |
| 3 | 12 | \(n \le 10\,000\) | – | \(t_i = 2\) | – | |
| 4 | 13 | – | – | – | – | В любой момент строка состоит только из скобок ( и ) |
| 5 | 20 | – | – | \(t_i = 2\) | 3 | |
| 6 | 24 | – | – | – | 0 – 5 | Offline-проверка. |
6 )()(() 7 2 1 6 1 4 ) 2 2 5 1 3 [ 1 4 ] 2 1 6 2 4 5
Yes Yes Yes No
10
>())(][<}{
6
2 1 10
1 3 (
2 1 10
2 2 5
1 2 )
2 1 10Yes No No Yes