题目描述
给定一个长度为 n 的合法括号序列 S。 称一个区间 [l,r] 是合法的当且仅当翻转区间 [l,r] 内的字符后 S 仍是一个合法括号序列。 求有多少区间 [l,r] 是合法的。 注:翻转指前后翻转,即将 al,al+1,…,ar 变为 ar,ar−1,…,al。
输入格式
一行一个字符串表示给定的括号序列 S。
输出格式
一行一个整数表示合法区间数量。
样例输入
()()
样例输出
7
样例解释
合法的区间有 [1,1],[1,3],[2,2],[2,3],[2,4],[3,3],[4,4]。
数据范围
记 k 为最大括号嵌套层数。
对于所有测试数据,1≤k≤n≤106。
| 子任务编号 |
分值 |
n |
k |
| 1 |
10 |
≤500 |
≤n |
| 2 |
30 |
≤5000 |
| 3 |
10 |
≤5⋅104 |
≤10 |
| 4 |
≤2⋅105 |
| 5 |
≤5⋅104 |
≤n |
| 6 |
≤2⋅105 |
| 7 |
20 |
≤106 |