| Codeforces Round 765 (Div. 2) |
|---|
| Закончено |
Это простая версия задачи. Единственным различием между простой и сложной версиями задачи является наличие запросов удаления: они присутствуют лишь в сложной версии.
Компания «Interplanetary Software, Inc.» вместе с компанией «Robots of Cydonia, Ltd.» разработала и выпустила роботов-котов. Эти электронные питомцы умеют мяукать, ловить мышей и всячески развлекать хозяина.
Недавно разработчики из «Interplanetary Software, Inc.» решили выпустить обновление программного обеспечения для этих роботов. После обновления коты должны уметь решать задачи, связанные со скобочными последовательностями. Одна из таких задач приведена ниже.
Сначала немного погрузимся в теорию скобочных последовательностей. Будем рассматривать строки, состоящие из символов «(», «)» и «.». Назовем строку правильной скобочной последовательностью (ПСП), если из нее можно получить пустую строку путем операций удаления одиночных символов «.» либо подряд идущих символов «()». Например, строка «(()(.))» является ПСП, т. к. с ней можно проделать следующую цепочку удалений:
Мы получили пустую строку, а это значит, что исходная строка является ПСП. В то же время, строка «)(» не является ПСП, поскольку к ней нельзя применить описанные выше операции удаления.
Будем называть ПСП простой, если эта ПСП непуста, не начинается на «.» и не заканчивается на «.».
Также будем считать, что подстрока строки $$$s$$$ — это ее последовательный подотрезок. В частности, $$$s[l\dots r] = s_ls_{l+1}\dots s_r$$$, где $$$s_i$$$ — $$$i$$$-й символ строки $$$s$$$.
Теперь перейдем к формулировке задачи. Вам дана строка $$$s$$$, изначально состоящая из символов «(» и «)». Необходимо отвечать на запросы следующего вида.
Даны индексы $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$), причем гарантируется, что подстрока $$$s[l\dots r]$$$ — простая ПСП. Требуется найти количество подстрок в $$$s[l\dots r]$$$, которые являются простыми ПСП. Иными словами, необходимо найти количество пар индексов $$$i$$$, $$$j$$$ таких, что $$$l \le i < j \le r$$$ и $$$s[i\dots j]$$$ является простой ПСП.
Вы работаете в «Interplanetary Software, Inc.» и Вам поручили непростое задание: научить котов после обновления решать описанную выше задачу.
Обратите внимание, что в данной версии задачи в строке не может появиться символ «.». Он нужен лишь для сложной версии задачи.
В первой строке входных данных находится два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 3\cdot10^5$$$, $$$1 \le q \le 3\cdot10^5$$$) — длина строки и количество запросов.
Во второй строке находится строка $$$s$$$, состоящая из $$$n$$$ символов «(» и «)».
В каждой из следующих $$$q$$$ строк находится по три целых числа $$$t$$$, $$$l$$$ и $$$r$$$ ($$$t = 2$$$, $$$1 \le l < r \le n$$$) — запросы, которые требуется обработать. Гарантируется, что все запросы корректны и удовлетворяют условию задачи. Обратите внимание, что в данной задаче число $$$t$$$ не используется и всегда равно двум. Оно необходимо для сложной версии задачи.
Для каждого запроса выведите по одному целому числу в отдельной строке — количество подстрок, которые являются простыми ПСП. Ответы требуется выводить в том же, порядке, в котором приведены сами запросы.
9 4 )(()())() 2 3 6 2 2 7 2 8 9 2 2 9
3 4 1 6
Рассмотрим пример из условия.
Ответ на первый запрос равен $$$3$$$, поскольку существует всего три требуемых подстроки: $$$s[3\dots6]$$$, $$$s[3\dots4]$$$ и $$$s[5\dots6]$$$.
Ответ на второй запрос равен $$$4$$$. Подходящие подстроки — $$$s[3\dots6]$$$, $$$s[3\dots4]$$$, $$$s[5\dots6]$$$ и $$$s[2\dots7]$$$.
Ответ на третий запрос равен $$$1$$$. Подходящая подстрока — $$$s[8\dots9]$$$.
Ответ на четвертый запрос равен $$$6$$$. Подходящие подстроки — $$$s[3\dots6]$$$, $$$s[3\dots4]$$$, $$$s[5\dots6]$$$, $$$s[2\dots7]$$$, $$$s[8\dots9]$$$ и $$$s[2\dots9]$$$.
