Bracket Cost

题意翻译

给你一个长度为 $n$ 的括号序列。 我们能对一个括号序列做以下操作： - 选择一个**子串**，将其循环右移一位。比如，`(())` 循环右移一位之后变为 `)(()`。 - 在括号序列的**任意位置**加一个左括号或右括号。 我们定义一个括号序列的代价为能将其变为**匹配序列**的最少操作次数。 求这个括号序列所有 $\frac{n(n-1)}{2}$ 的**子串的代价之和**。（子串互相独立） 多组数据。$n\le 2\times 10^5$。

题目描述

Daemon Targaryen decided to stop looking like a Metin2 character. He turned himself into the most beautiful thing, a bracket sequence. For a bracket sequence, we can do two kind of operations: - Select one of its substrings $ ^\dagger $ and cyclic shift it to the right. For example, after a cyclic shift to the right, "(())" will become ")(()"; - Insert any bracket, opening '(' or closing ')', wherever you want in the sequence. We define the cost of a bracket sequence as the minimum number of such operations to make it balanced $ ^\ddagger $ . Given a bracket sequence $ s $ of length $ n $ , find the sum of costs across all its $ \frac{n(n+1)}{2} $ non-empty substrings. Note that for each substring we calculate the cost independently. $ ^\dagger $ A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. $ ^\ddagger $ A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $ + $ and $ 1 $ . For example, sequences "(())()", "()", and "(()(()))" are balanced, while ")(", "(()", and "(()))(" are not.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the bracket sequence. The second line of each test case contains a string $ s $ , consisting only of characters '(' and ')', of length $ n $ — the bracket sequence. It is guaranteed that sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the sum of costs of all substrings of $ s $ .

输入输出样例

输入样例 #1

5
1
)
4
)()(
3
())
5
(((((
10
)(())))())

输出样例 #1

1
9
6
35
112

说明

In the first test case, there is the only substring ")". Its cost is $ 1 $ because we can insert '(' to the beginning of this substring and get a string "()", that is a balanced string. In the second test case, the cost of each substring of length one is $ 1 $ . The cost of a substring ")(" is $ 1 $ because we can cyclically shift it to right and get a string "()". The cost of strings ")()" and "()(" is $ 1 $ because its enough to insert one bracket to each of them. The cost of substring ")()(" is $ 1 $ because we can cyclically shift it to right and get a string "()()". So there are $ 4 + 2 + 2 + 1 = 9 $ substring of cost $ 1 $ and $ 1 $ substring of cost $ 0 $ . So the sum of the costs is $ 9 $ . In the third test case, - "(", the cost is $ 1 $ ; - "()", the cost is $ 0 $ ; - "())", the cost is $ 1 $ ; - ")", the cost is $ 1 $ ; - "))", the cost is $ 2 $ ; - ")", the cost is $ 1 $ . So the sum of the costs is $ 6 $ .

**括号成本**

**题意翻译**
给你一个长度为 $ n $ 的括号序列。

我们能对一个括号序列做以下操作：

- 选择一个**子串**，将其循环右移一位。比如，`(())` 循环右移一位之后变为 `)(()`。
- 在括号序列的**任意位置**加一个左括号或右括号。

我们定义一个括号序列的代价为能将其变为**匹配序列**的最少操作次数。

求这个括号序列所有 $ \frac{n(n-1)}{2} $ 的**子串的代价之和**。（子串互相独立）

多组数据。$ n \le 2 \times 10^5 $。

**题目描述**
Daemon Targaryen决定不再看起来像一个Metin2角色。他变成了最美妙的东西，一个括号序列。

对于一个括号序列，我们可以进行两种操作：

- 选择它的一个子串 $ ^\dagger $ 并将其循环右移。例如，经过一次向右的循环移位后，"(())" 将变为 ")(()"；
- 在序列的任意位置插入任何括号，开放的 '(' 或关闭的 ')'。

我们定义一个括号序列的代价为使其平衡 $ ^\ddagger $ 所需的最少此类操作数。

给定一个长度为 $ n $ 的括号序列 $ s $，找出所有 $ \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 $ 所有子串的代价之和。

**输入输出样例**

**输入样例 #1**
```
5
1
)
4
)()(
3
())
5
((((((
10
)(())))())
```

**输出样例 #1**
```
1
9
6
35
112
```

**说明**
在第一个测试用例中，只有一个子串 " )"。它的代价是 $ 1 $，因为我们可以在这个子串的开头插入 '(' 并得到字符串 "()"，这是一个平衡的字符串。

在第二个测试用例中，长度为1的每个子串的代价是 $ 1 $。" )(" 的代价是 $ 1 $，因为我们可以循环右移它并得到字符串 "()"。" )() " 和 " ()(" 的代价是 $ 1 $，因为它们各自只需要插入一个括号。" )()(" 的代价是 $ 1 $，因为我们可以循环右移它并得到字符串 " ()() "。所以有 $ 4 + 2 + 2 + 1 = 9 $ 个代价为 $ 1 $ 的子串和 $ 1 $ 个代价为 $ 0 $ 的子串。所以代价之和是 $ 9 $。

在第三个测试用例中，

- " ("，代价是 $ 1 $；
- "()"，代价是 $ 0 $；
- "())"，代价是 $ 1 $；
- ")"，代价是 $ 1 $；
- "))"，代价是 $ 2 $；
- ")"，代价是 $ 1 $。

所以代价之和是 $ 6 $。**括号成本** **题意翻译** 给你一个长度为 $ n $ 的括号序列。 我们能对一个括号序列做以下操作： - 选择一个**子串**，将其循环右移一位。比如，`(())` 循环右移一位之后变为 `)(()`。 - 在括号序列的**任意位置**加一个左括号或右括号。 我们定义一个括号序列的代价为能将其变为**匹配序列**的最少操作次数。 求这个括号序列所有 $ \frac{n(n-1)}{2} $ 的**子串的代价之和**。（子串互相独立） 多组数据。$ n \le 2 \times 10^5 $。 **题目描述** Daemon Targaryen决定不再看起来像一个Metin2角色。他变成了最美妙的东西，一个括号序列。 对于一个括号序列，我们可以进行两种操作： - 选择它的一个子串 $ ^\dagger $ 并将其循环右移。例如，经过一次向右的循环移位后，"(())" 将变为 ")(()"； - 在序列的任意位置插入任何括号，开放的 '(' 或关闭的 ')'。 我们定义一个括号序列的代价为使其平衡 $ ^\ddagger $ 所需的最少此类操作数。 给定一个长度为 $ n $ 的括号序列 $ s $，找出所有 $ \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 $ 所有子串的代价之和。 **输入输出样例** **输入样例 #1** ``` 5 1 ) 4 )()( 3 ()) 5 (((((( 10 )(())))()) ``` **输出样例 #1** ``` 1 9 6 35 112 ``` **说明** 在第一个测试用例中，只有一个子串 " )"。它的代价是 $ 1 $，因为我们可以在这个子串的开头插入 '(' 并得到字符串 "()"，这是一个平衡的字符串。 在第二个测试用例中，长度为1的每个子串的代价是 $ 1 $。" )(" 的代价是 $ 1 $，因为我们可以循环右移它并得到字符串 "()"。" )() " 和 " ()(" 的代价是 $ 1 $，因为它们各自只需要插入一个括号。" )()(" 的代价是 $ 1 $，因为我们可以循环右移它并得到字符串 " ()() "。所以有 $ 4 + 2 + 2 + 1 = 9 $ 个代价为 $ 1 $ 的子串和 $ 1 $ 个代价为 $ 0 $ 的子串。所以代价之和是 $ 9 $。 在第三个测试用例中， - " ("，代价是 $ 1 $； - "()"，代价是 $ 0 $； - "())"，代价是 $ 1 $； - ")"，代价是 $ 1 $； - "))"，代价是 $ 2 $； - ")"，代价是 $ 1 $。 所以代价之和是 $ 6 $。