← 返回题目列表

Codeforces · 1750/E

E. 支架成本

中文机器翻译题面 查看原题

戴蒙·坦格利安决定不再看起来像 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$$$。