← 返回题目列表

Codeforces · 1976/D

D. 可反转括号序列

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

常规括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如:

- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。

让我们定义括号序列的逆序列如下:将所有括号 '(' 替换为 ')',反之亦然(所有括号 ')' 替换为 '(')。例如,字符串“()((”和“)())”彼此相反。

给你一个常规的括号序列$$$s$$$。计算整数对 $$$(l,r)$$$ ($$$1 \le l \le r \le |s|$$$) 的数量,这样,如果将 $$$s$$$ 的子字符串从第 $$$l$$$ 字符替换为第 $$$r$$$ 字符(包括),则 $$$s$$$ 仍将是常规括号序列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例唯一一行包含非空正则括号序列;它仅由字符“(”和/或“)”组成。

对输入的附加约束:所有测试用例的常规括号序列的总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 满足语句中条件的 $$$(l,r)$$$ 对的数量。

示例

输入 #1

4
(())
()
()()()
(()())(())

输出 #1

1
0
3
13

注意

在第一个示例中,只有一对:

- $$$(2, 3)$$$: (()) $$$\rightarrow$$$ ()()。

在第二个示例中,没有对。

在第三个示例中,有三对:

- $$$(2, 3)$$$: ()()() $$$\rightarrow$$$ (())();
- $$$(4, 5)$$$: ()()() $$$\rightarrow$$$ ()(());
- $$$(2, 5)$$$: ()()() $$$\rightarrow$$$ (()());