#P17713. [2026年江苏省队集训]括号序列

[2026年江苏省队集训]括号序列

题目描述

给定一个长度为 nn 的合法括号序列 SS。 称一个区间 [l,r][l,r] 是合法的当且仅当翻转区间 [l,r][l,r] 内的字符后 SS 仍是一个合法括号序列。 求有多少区间 [l,r][l,r] 是合法的。 注:翻转指前后翻转,即将 al,al+1,…,ara_l,a_{l+1},\dots,a_r 变为 ar,ar−1,…,ala_r,a_{r-1},\dots,a_l。

输入格式

一行一个字符串表示给定的括号序列 SS。

输出格式

一行一个整数表示合法区间数量。

样例输入

()()

样例输出

7

样例解释

合法的区间有 [1,1],[1,3],[2,2],[2,3],[2,4],[3,3],[4,4][1,1],[1,3],[2,2],[2,3],[2,4],[3,3],[4,4]。

数据范围

记 kk​ 为最大括号嵌套层数。

对于所有测试数据,1≤k≤n≤1061\leq k \leq n\leq 10^6。

子任务编号 分值 n k
1 10 ≤500\leq 500 ≤n\leq n
2 30 ≤5000\leq 5000
3 10 ≤5⋅104\leq 5\cdot 10^4 ≤10\leq 10
4 ≤2⋅105\leq 2\cdot 10^5
5 ≤5⋅104\leq 5\cdot 10^4 ≤n\leq n
6 ≤2⋅105\leq 2\cdot 10^5
7 20 ≤106\leq 10^6