求合法括号子序列个数

题意

背景

合法括号串的定义如下：

1. () 是合法括号串。
2. 如果 A 是合法括号串，则 (A) 是合法括号串。
3. 如果 A，B 是合法括号串，则 AB 是合法括号串。

子串与不同的子串的定义如下：

1. 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 \(l\) 与终止位置 \(r\) 来表示，记为 \(S (l, r)\)（\(1 \leq l \leq r \leq |S |\)，\(|S |\) 表示 S 的长度）。
2. S 的两个子串视作不同当且仅当它们在 S 中的位置不同，即 \(l\) 不同或 \(r\) 不同。

题目

给出一个括号串 \(s\)（其不一定是合法括号串），问 \(s\) 中有多少个互不相同的子串是合法括号串。

样例

样例输入

(()()

样例输出

2

分析

观察序列1：

()()()

\(pos = 2\) 的时候，对答案的贡献值为 \(1\) 。

\(pos = 4\) 的时候，本身 \([3, 4]\) 就有一个满足要求的括号序列，再合并上前面的成为 \([1, 4]\) ，于是对答案的贡献值就为 \(2\) ，再加上前面 \([1, 2]\) 本身有的括号序列，总共为 \(3\)。

\(pos = 6\) 时，总共的贡献值为 \(3\) ，加上前面的有 \(3 + 3 = 6\) 种。其他位置均没有贡献（左括号没有贡献值）。

总之，\(pos\) 为 \(1 \sim 6\) 时对答案的贡献分别为 \(0, 1, 0, 2, 0, 3\) ，合并后的总答案为 \(0, 1, 1, 3, 3, 6\) 。

观察序列2：

())()

\(pos = 2\) 时，对答案贡献为 \(1\) 。

\(pos = 3\) 时，由于不满足成匹配的括号序列，所以没有贡献（我们只看右括号的贡献值）。

\(pos = 5\) 时，由于 \(pos = 3\) 时多了一个后括号，所以 \([1, 3]\) 不匹配，导致 \([1, 5]\) 成不了一个匹配的括号序列，所以对答案的贡献仍为 \(1\)

\(pos\) 为 \(1 \sim 5\) 时对答案的贡献分别为 \(0, 1, 0, 0, 1\) ，合并后的总答案为 \(0, 1, 1, 1, 2\) 。

观察序列3：

()(())

\(pos = 2\) 时，贡献为 \(1\) 。

\(pos = 5\) 时，由于 \(pos = 3\) 是在中间断开，所以 \([1, 5]\) 不能匹配，所以贡献仍为 \(1\) 。

\(pos = 6\) 时，我们发现 \([1, 2]\) 是匹配的。故 \([1, 2], [3, 6]\) 能合成一个匹配的序列，所以对答案贡献为 \(2\) 。

\(pos\) 为 \(1 \sim 6\) 时对答案的贡献分别为 \(0, 1, 0, 0, 1, 2\) ，合并后的总答案为 \(0, 1, 1, 1, 2, 4\) 。

可以发现，一个后括号如果能匹配一个前括号，假设这个前括号的前1位同样有一个已经匹配了的后括号，那么我们就可以把当前的匹配括号序列和之前的匹配括号序列合并。当前的这个后括号的贡献值，其实就等于前面那个后括号的贡献值 + 1。

Elaina's Code

int sum=0,tot[N];
string s;
stack<int> sta;
signed main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='(') sta.push(i);
		if(s[i]==')'){
			if(!sta.empty()){
				int l=sta.top();
				sta.pop();
				tot[i]=tot[l-1]+1;
			}
		}
		sum+=tot[i];
	}
	cout<<sum;
	return Elaina;
}