CF917A The Monster

由于 Will 被困在了“颠倒世界”中，但他依然可以通过圣诞灯（他可以用意念控制灯的开关）与他的妈妈 Joyce 沟通。他不能直接告诉妈妈自己在哪里，因为带走他的怪兽会得知他的下落并将其转移。 因此，他想出了一个谜题来告诉妈妈他的坐标。他的坐标正是以下问题的答案。 只包含括号（'(' 和 ')'）的字符串被称为括号序列（bracket sequence）。某些括号序列称为正确括号序列。更正式地定义如下： - 空字符串是正确括号序列。 - 如果 $s$ 是正确括号序列，那么 $ (s) $ 也是正确括号序列。 - 如果 $s$ 和 $t$ 是正确括号序列，那么 $st$（$s$ 与 $t$ 的连接）也是正确括号序列。 只包含括号和问号（'?'）的字符串，被定义为“漂亮”（pretty），当且仅当存在一种方法，把每个问号替换成 '(' 或 ')'，使得结果字符串成为非空的正确括号序列。 Will 通过圣诞灯用摩斯密码把一个只包含括号和问号的字符串 $s$ 传递给了妈妈。坐标即为满足 $1 \le l \le r \le |s|$ 的整数对 $(l, r)$ 的数量，使得子串 $s_{l} s_{l+1} \dots s_{r}$ 是漂亮的，其中 $s_{i}$ 表示 $s$ 的第 $i$ 个字符。 Joyce 对括号序列一无所知，所以她找到了你来帮忙。

输入的唯一一行包含字符串 $s$，其仅由字符 '('、')' 和 '?' 组成（$2 \le |s| \le 5000$）。

输出 Will 谜题的答案，即符合条件的 $(l, r)$ 对的数量。

对于第一个样例测试，$s$ 的漂亮子串为： 1. "(?" 可以被转换为 "()"。 2. "?)" 可以被转换为 "()"。 3. "((?)" 可以被转换为 "(())"。 4. "(?))" 可以被转换为 "(())"。 对于第二个样例测试，$s$ 的漂亮子串为： 1. "??" 可以被转换为 "()"。 2. "()"。 3. "??()" 可以被转换为 "()()"。 4. "?()?" 可以被转换为 "(())"。 5. "??" 可以被转换为 "()"。 6. "()??" 可以被转换为 "()()"。 7. "??()??" 可以被转换为 "()()()"。 由 ChatGPT 5 翻译