← 返回题目列表

AtCoder · bitflyer2018_final_c

C. 子字符串和括号

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

配点 : 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