记录编号	361493	评测结果	AAAAAAAAAA
题目名称	papertask	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.691 s
提交时间	2017-01-04 11:25:21	内存使用	43.22 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1000010;
long long ans;
char s[N];
int n,S[N],size,match[N],fa[N];
vector<int> Q[N];
void makepair(){
	for (int i=1;i<=n;i++)
		S[++size]=0,s[i]-='(';
	for (int i=1;i<=n;i++)
	if (s[i]) match[i]=S[size--];
		else S[++size]=i;
	for (int i=n;i;i--)
	if (s[i]&&!fa[i]){
		int now=i;
		do{
			fa[now]=i;
			now=match[now]-1;
			Q[i].push_back(now+1);
		}while (now&&s[now]);
		Q[i].push_back(-1);
		int len=Q[i].size()-1;
		for (int j=len;j;j--)
		if (j>len-j) swap(Q[i][j],Q[i][len-j]);
		/*printf("%d:\n",i);
		for (int j=0;j<Q[i].size();j++) printf("%d ",Q[i][j]);
		puts("");*/
	}
}
int find(int i,int x){
	i=fa[i];
	if (Q[i].empty()) return 0;
	int l=0,r=Q[i].size()-1;
	while (l!=r){
		int mid=(l+r)>>1;
		if (Q[i][mid+1]<=x) l=mid+1;else r=mid;
	}
	return l;
}
int go[N][2],len[N],par[N],Right[N],last,top;
int New(int L){len[++top]=L;return top;}
void extend(int n){
	int w=s[n],p=last,np=New(len[p]+1);
	Right[np]=n;
	while (p&&!go[p][w]) go[p][w]=np,p=par[p];
	if (!p) par[np]=1;
	else{
		int q=go[p][w];
		if (len[q]==len[p]+1) par[np]=q;
		else{
			int nq=New(len[p]+1);
			Right[nq]=n;
			memcpy(go[nq],go[q],sizeof go[q]);
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while (p&&go[p][w]==q) go[p][w]=nq,p=par[p];
		}
	}
	ans+=find(n,n-len[par[np]])-find(n,n-len[np]);
	last=np;
}
int main()
{
	freopen("papertask.in","r",stdin);
	freopen("papertask.out","w",stdout);
	scanf("%d%s",&n,s+1);
	makepair();
	last=New(0);
	for (int i=1;i<=n;i++) extend(i);
	printf("%lld\n",ans);
	return 0;
}