配点 : 500 点
問題文
( 和 ) 会得到由...组成的字符串 S 给定整数,满足以下条件 (i,j) (1 ≤ i ≤ j ≤ |S|的组合有多少。
条件: - S 的 i 从第一个字符开始 j 取到第...个字符为止(包含两端)时,该字符串为括号匹配的。
括号匹配的字符串是满足以下任一条件的字符串。
- 空文字列
- 存在某个括号完全匹配的字符串 A, B , A, B 按此顺序连接的字符串
- 存在某个括号完全匹配的字符串 A ,
(, A,)按此顺序连接的字符串
制約
- 1 ≤ |S| ≤ 10^5
- S 满足
(,)构成的唯一字符串
入力
输入将以以下形式从标准输入给出。
S
出力
满足条件的整数 (i,j) (1 ≤ i ≤ j ≤ |S|) 的组的个数。
入力例 1
((())
出力例 1
2
- S 的 2 从第一个字符开始 5 取到第几个字符时,
(())是。这个括号是配对的。 - S 的 3 从第一个字符开始 4 取到第几个字符时,
()是。这个括号是配对的。
因此, (2, 5) 和 (3, 4) 满足条件。
入力例 2
(()()(())(
出力例 2
7