Деймон Таргариен решил перестать быть похожим на персонажа Metin2. Он превратил себя в прекраснейшую вещь — скобочную последовательность.
Для последовательности скобок мы можем выполнять два вида операций:
Мы определяем стоимость скобочной последовательности как минимальное количество таких операций, чтобы сделать её правильной$$$^\ddagger$$$.
Для заданной скобочной последовательности $$$s$$$ длины $$$n$$$ найдите сумму стоимостей всех $$$\frac{n(n+1)}{2}$$$ её непустых подстрок. Обратите внимание, что для каждой подстроки мы вычисляем стоимость независимо.
$$$^\dagger$$$ Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
$$$^\ddagger$$$ Последовательность скобок называется правильной, если её можно превратить в правильное математическое выражение, добавив символы $$$+$$$ и $$$1$$$. Например, последовательности «(())()», «()» и «(()(()))» правильные, в то время как «)(», «(()» и «(()))(» не являются правильными.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину скобочной последовательности.
Вторая строка каждого набора входных данных содержит строку $$$s$$$, состоящую только из символов '(' и ')', длины $$$n$$$ — скобочную последовательность.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное целое число — сумму стоимостей всех подстрок $$$s$$$.
51)4)()(3())5(((((10)(())))())
1 9 6 35 112
В первом наборе входных данных есть единственная подстрока «)». Её стоимость $$$1$$$, потому что мы можем вставить «(» в начало этой подстроки и получить строку «()», то есть сбалансированную строку.
Во втором наборе входных данных стоимость каждой подстроки длины один равна $$$1$$$. Стоимость подстроки «)(» равна $$$1$$$, потому что мы можем циклически сдвинуть ее вправо и получить строку «()». Стоимость строк « )()» и «()(» равна $$$1$$$, потому что достаточно вставить по одной скобке в каждую из них. Стоимость подстроки «)()(» равна $$$1$$$, потому что мы можем циклически сдвинуть её вправо и получить строку «()()». Таким образом, есть $$$4 + 2 + 2 + 1 = 9$$$ подстрока стоимостью $$$1$$$ и $$$1$$$ подстрока из стоимостью $$$0$$$. Таким образом, сумма стоимостей равна $$$9$$$.
В третьем наборе входных данных:
Таким образом, сумма стоимостей равна $$$6$$$.
Название |
---|