【Codeforces 653F】Paper task

  评论区里有关于这题的SAM做法，可惜我智商低下，看不懂。

  一个比较显然的做法，对于每个位置，计算以该点为起始点的子串中合法的括号序列数。这个预处理出每个点前面（包括这个点）左括号比右括号多多少个，值一样的区间就是合法区间。

  这个只要建出后缀数组，以第sa[i]个字符为起始点的子串与第sa[i-1]个字符为起始点的子串的重复内容长度为h[i]，计算时记得把这段重复内容减去。

  然后用一个线段树维护一下合法的最长的长度就好了。

  官方题解里还有一种用Trie树做的做法。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> Point;
const int maxn=500010,inf=~0u>>1;

int Build_SA(char *ch,int n,int *sa,int *rank,int *h)
{
	static int cnt[maxn],temp1[maxn],temp2[maxn],*x,*y,p,m=128,i,j;
	x=temp1,y=temp2;
	for (i=0;i<=m;i++) cnt[i]=0;
	for (i=1;i<=n;i++) cnt[x[i]=ch[i]]++;
	for (i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for (i=n;i;i--) sa[cnt[ch[i]]--]=i;
	for (j=1;;j<<=1)
	{
		p=0;
		for (i=n-j+1;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
		for (i=0;i<=m;i++) cnt[i]=0;
		for (i=1;i<=n;i++) cnt[x[y[i]]]++;
		for (i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for (i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i];
		swap(x,y);p=1;
		x[sa[1]]=1;
		for (i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j])?p:++p;
		if (p==n) break;
		m=p;
	}
	for (i=1;i<=n;i++) rank[sa[i]]=i;

	for (i=1,p=0;i<=n;i++)
	{
		if (p) p--;
		j=sa[rank[i]-1];
		while (ch[j+p]==ch[i+p]) p++;
		h[rank[i]]=p;
	}
}

struct Segment_Tree
{
	int minval[maxn<<2];
	int n;

	#define ls (o<<1)
	#define rs (o<<1|1)
	#define mid ((l+r)>>1)

	void Update(int o) {minval[o]=min(minval[ls],minval[rs]);}

	void Build_Tree(int o,int l,int r,int *sum)
	{
		if (l==r) {minval[o]=sum[l];return;}
		Build_Tree(ls,l,mid,sum);
		Build_Tree(rs,mid+1,r,sum);
		Update(o);
	}

	int Query(int o,int l,int r,int a,int b)
	{
		if (a<=l && r<=b) return minval[o];
		int res=inf;
		if (a<=mid) res=min(res,Query(ls,l,mid,a,b));
		if (b> mid) res=min(res,Query(rs,mid+1,r,a,b));
		return res;
	}

	void Build_Tree(int *sum,int _n)
	{
		n=_n;
		Build_Tree(1,1,n,sum);
	}

	int Query(int l,int r)
	{
		return Query(1,1,n,l,r);
	}
	#undef ls
	#undef rs
	#undef mid
}T;

int sa[maxn],rank[maxn],h[maxn];
Point C[maxn];
int sum[maxn];
char ch[maxn];
int n;
long long ans;

int main()
{
	scanf("%d",&n);
	scanf("%s",ch+1);
	Build_SA(ch,n,sa,rank,h);
	for (int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+((ch[i]=='(')?1:-1);
		C[i]=make_pair(sum[i],i);
	}
	sort(C+1,C+1+n);
	T.Build_Tree(sum,n);
	for (int i=1;i<=n;i++) if (ch[i]=='(')
	{
		int l=i,r=n,mid;
		while (l<r)
			if (T.Query(i,mid=((l+r+1)>>1))<sum[i-1]) r=mid-1;else l=mid;
		if (l-i+1<=h[rank[i]]) continue;
		ans+=lower_bound(C+1,C+1+n,make_pair(sum[i-1],l+1))-lower_bound(C+1,C+1+n,make_pair(sum[i-1],i+h[rank[i]]));
	}
	printf("%I64d\n",ans);
	return 0;
}