AT_bitflyer2018_final_c 部分文字列と括弧

给定一个只由 `(` 和 `)` 组成的字符串 $S$。请计算有多少组整数 $(i, j)$（$1 \leq i \leq j \leq |S|$）满足下述条件。 条件：取出 $S$ 的第 $i$ 个字符到第 $j$ 个字符（包括两端），所得的子串是**括号匹配的字符串**。 **括号匹配的字符串**定义如下，满足以下任一条件的字符串为括号匹配的字符串： - 空字符串； - 存在括号匹配的字符串 $A$、$B$，将 $A$ 和 $B$ 按顺序连接得到的字符串； - 存在括号匹配的字符串 $A$，将 `(`、$A$、`)` 按顺序连接得到的字符串。

输入为一行，包含一个字符串 $S$。

输出满足条件的整数对 $(i, j)$（$1 \leq i \leq j \leq |S|$）的个数。

## 限制 - $1 \leq |S| \leq 10^5$ - $S$ 仅由 `(` 和 `)` 组成 ## 样例解释 1 - 取 $S$ 的第 $2$ 个字符到第 $5$ 个字符，得到 `(())`，这是括号匹配的字符串。 - 取 $S$ 的第 $3$ 个字符到第 $4$ 个字符，得到 `()`，这也是括号匹配的字符串。 因此，$(2, 5)$ 和 $(3, 4)$ 满足条件。 由 ChatGPT 4.1 翻译