【JZOJ4209】已经没有什么好害怕的了【差分】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/4209
给出一个括号序列，设$ans_i$表示经过$i$的合法的串，合法的串指所有括号都可以匹配且没有穿插。

---

思路:

设$next[i]$表示与（前括号）$i$相匹配的后括号位置，$last[i]$表示与（后括号）$i$相匹配的前括号的位置。这个可以用栈$O(n)$求出。
假设这个序列是这样的
$())((())())(())$
先只看最外层的括号
$())(......)(......)$
将无用的括号分离
$() | (......)(......)$
会发现，每个括号所影响到的组数是递增的。
而每个后括号影响是递减的。
于是就用差分维护。
然后对于括号内的，再递归求解即可。
每个括号最多访问两次，时间复杂度$O(n)$。

---

代码：

#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

const int MOD=1000000007;
const int N=1000010;
int T,len,next[N],last[N];
char ch[N];
ll sum[N],ans;

void work1(int l,int r)  //前括号差分
{
	if (l>r) return;
	ll k=0;
	for (int i=r;i>=l;i--)
		if (last[i])
		{
			work1(last[i]+1,i-1);  //递归
			k++;
			sum[last[i]]+=k;
			i=last[i];
		}
		else k=0;
}

void work2(int l,int r)  //后括号
{
	if (l>r) return;
	ll k=0;
	for (int i=l;i<=r;i++)
		if (next[i])
		{
			work2(i+1,next[i]-1);
			k++;
			sum[next[i]+1]-=k;
			i=next[i];
		}
		else k=0;
}

int main()
{
	scanf("%d",&T);
	while (T--)
	{
		memset(sum,0,sizeof(sum));
		memset(next,0,sizeof(next));
		memset(last,0,sizeof(last));
		memset(sum,0,sizeof(sum));
		scanf("%s",ch+1);
		len=strlen(ch+1);
		stack<int> s;
		for (int i=1;i<=len;i++)
			if (ch[i]=='(') s.push(i);
				else if (s.size())
				{
					next[s.top()]=i;
					last[i]=s.top();  //利用栈求
					s.pop();
				}
		work1(1,len);
		work2(1,len);
		ans=0;
		for (int i=1;i<=len;i++)
		{
			sum[i]+=sum[i-1];
			ans+=sum[i]*(ll)i%MOD;
		}
		cout<<ans<<endl;
	}
	return 0;
}