CF1750E Bracket Cost

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$）——括号序列的长度。 第二行包含一个长度为 $n$ 的只由 '(' 和 ')' 组成的字符串 $s$——括号序列。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——$s$ 的所有子串的代价之和。

在第一个测试用例中，唯一的子串是 ")"。其代价为 $1$，因为我们可以在该子串开头插入一个 '('，得到 "()"，这是一个平衡序列。 在第二个测试用例中，每个长度为 $1$ 的子串代价都是 $1$。子串 ")(" 的代价为 $1$，因为我们可以将其循环右移得到 "()"。子串 ")()" 和 "()(" 的代价都是 $1$，因为只需插入一个括号即可。子串 ")()(" 的代价为 $1$，因为我们可以将其循环右移得到 "()()"。所以共有 $4 + 2 + 2 + 1 = 9$ 个代价为 $1$ 的子串，$1$ 个代价为 $0$ 的子串。因此总代价为 $9$。 在第三个测试用例中： - "("，代价为 $1$； - "()"，代价为 $0$； - "())"，代价为 $1$； - ")"，代价为 $1$； - "))"，代价为 $2$； - ")"，代价为 $1$。 所以总代价为 $6$。 由 ChatGPT 4.1 翻译