406418: GYM102399 B Личность широких взглядов
Description
Вася — опытный составитель задач для олимпиад по программированию. На его счету множество разнообразнейших задач, с некоторыми из которых вы можете быть знакомы. Как и все великие творцы, Вася столкнулся с творческим кризисом.
Задачу-то Вася придумал, но не может никак придумать остроумную и уместную легенду к этой задаче. Уже который день Вася не выходит из комнаты, он падает в пучину отчаяния, ужаса, одиночества и безнадёжности. Чтобы как-то его развеселить, друг Петя подарил ему строку $$$s$$$, состоящую только из открывающих и закрывающих скобок.
«Ну вот, — подумал Вася, — опять главному герою подарили что-то, чего в реальной жизни никто не дарит. Сейчас, видимо, ещё какое-нибудь свойство припишут этой строке, которое нужно будет вычислить.»
Красотой строки из скобок называется количество её циклических сдвигов, которые являются правильной скобочной последовательностью.
«Вау, как оригинально, — скептически пробурчал себе под нос Вася, — ни разу не видел, чтобы в задачах по программированию требовалось вычислять красоту целого объекта. Ну всё, сейчас мне зачем-то будет надо будет вычислять эту величину на подотрезках и обрабатывать какие-то запросы изменения строки.»
И в самом деле. Для запросов вида $$$(l, r)$$$ требовалось определить красоту подотрезка строки $$$s$$$ с $$$l$$$ по $$$r$$$ (включительно). Помимо этого, поступали запросы изменения определённых символов строки $$$s$$$.
«Замечательно, — разочарованно вздохнул Вася, — очередная скучная задача на структуры данных, не хочу её решать. О, а ведь можно дать эту задачу на какую-нибудь олимпиаду!»
Так Вася и поступил. Докажите Васе, что задача совсем не скучная и решите её.
Входные данныеВ первой строке задано целое число $$$n$$$ ($$$1 \leq n \leq 300\,000$$$) — длина строки $$$s$$$, которую подарили Васе.
Во второй строке задана строка $$$s$$$ длины $$$n$$$, состоящая только из символов «(» и «)».
В третьей строке задано целое число $$$q$$$ ($$$1 \leq q \leq 300\,000$$$) — количество запросов определения красоты подстроки.
В следующих $$$q$$$ строках заданы описания запросов. Запросы бывают двух видов:
- 1 x ($$$1 \leq x \leq n$$$). Требуется изменить символ строки $$$s$$$ на позиции $$$x$$$ на противоположный (то есть ( на ), а ) на ().
- 2 l r ($$$1 \leq l \leq r \leq n$$$). Требуется определить красоту подотрезка строки $$$s$$$ с символа $$$l$$$ по символ $$$r$$$ (включительно).
Для запросов второго типа выведите ответы на них в том порядке, в котором они заданы во входном файле.
ПримерВходные данные10 )(()()())( 6 2 1 10 2 3 6 1 4 2 2 7 1 5 2 3 6Выходные данные
2 2 0 1Примечание
Напомним, что правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.
Циклическим сдвигом строки $$$s$$$ длины $$$n$$$ на $$$k$$$ ($$$0 \leq k < n$$$) называется строка, являющая собой конкатенацию (сложение) последних $$$k$$$ символов строки (суффикса длины $$$k$$$) $$$s$$$ и первых $$$n - k$$$ символов строки (префикса длины $$$n - k$$$). Два циклических сдвига на $$$i$$$ и $$$j$$$ называются различными, если $$$i \ne j$$$.
В первом запросе рассматривается строка )(()()())(. У неё есть два циклических сдвига, которые являются правильными скобочными последовательностями: сдвиг на $$$1$$$ и сдвиг на $$$9$$$.
Во втором запросе рассматривается строка ()(). У неё также есть два циклических сдвига, которые являются правильными скобочными последовательностями: сдвиг на $$$0$$$ и сдвиг на $$$2$$$.
После третьего запроса строка $$$s$$$ становится равной )(((()())(.
В четвёртом запросе рассматривается строка (((()(. Ни один из её циклических сдвигов не является правильной скобочной последовательностью.
После пятого запроса строка $$$s$$$ становится равной )((())())(.
В шестом запросе рассматривается строка (()). У неё есть только один циклический сдвиг на $$$0$$$.