本文共 2765 字，大约阅读时间需要 9 分钟。

题意

一个长度为$n$的括号串,求有多少本质不同的括号子串

括号序列的定义是在任何位置左括号的数量大于等于右括号的数量

那么把$($看作$1$,把$)$看作$-1$做前缀和$pre$数组

枚举左端点$l$,那么我们可以二分出一个$r$使得$[l,r]$的区间最小值大于等于$pre[l-1]$

因为中间有任何一个$pre[i]<pre[l-1]$都是不合法的,而区间最小值单调,可以二分

所以,以$l$为左端点的合法括号序列的右端点一定在$[l,r]$里面

于是当$i\in [l,r]$内找到有多少$pre[i]$等于$pre[l-1]$,那么这些点都可以作为右端点

所以我们把相同的$pre[i]$的下标装在一个桶$vector$数组中

查询$[l,r]$有多少直接在这个$vector$里面二分查找即可

如何去重???

考虑后缀数组,每次我们按照$sa[1],sa[2]...$的顺序加入所有后缀

为了不和前面重复,我二分的右端点应该大于等于$sa[i]+height[i]$

除此之外再无区别

#include 
   
    using namespace std;const int maxn = 3e6+10;const int base = 5e5;int n,m,c[maxn],x[maxn],y[maxn],sa[maxn],rk[maxn],height[maxn],pre[maxn];char a[maxn];void SA(){
   	m = 500;	for(int i=1;i<=n;i++)	c[x[i]=a[i]]++;	for(int i=1;i<=m;i++)	c[i] += c[i-1];	for(int i=n;i>=1;i--)	sa[c[x[i]]--] = i;	for(int k=1;k<=n;k<<=1 )	{
   		int num = 0;		for(int i=n-k+1;i<=n;i++)	y[++num] = i;		for(int i=1;i<=n;i++)	if( sa[i]>k )	y[++num] = sa[i]-k;		for(int i=0;i<=m;i++)	c[i] = 0;		for(int i=1;i<=n;i++)	c[x[i]]++;		for(int i=1;i<=m;i++)	c[i] += c[i-1];		for(int i=n;i>=1;i--)	sa[c[x[y[i]]]--] = y[i], y[i] = 0;		swap(x,y);		num = 1,x[sa[1]] = 1;		for(int i=2;i<=n;i++)			x[sa[i]] = ( y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] )?num:++num;		if( num==n )	break;		m = num;	}	for(int i=1;i<=n;i++)	rk[sa[i]] = i;	for(int i=1,k=0;i<=n;i++)	{
   		if( rk[i]==1 )	continue;		if( k )	k--;		int j = sa[rk[i]-1];		while( j+k<=n&&i+k<=n&&a[i+k]==a[j+k] )	k++;		height[rk[i]] = k;	}}vector
    
     vec[maxn];//桶 int st[maxn][22];void init(){
   	for(int i=1;i<=n;i++)	st[i][0] = pre[i];	for(int i=1;i<=20;i++)	for(int j=1;j+(1<
     
      <=n;j++)		st[j][i] = min( st[j][i-1],st[j+(1<<(i-1))][i-1] );}int get(int l,int r){
   	if( l>r )	swap(l,r);	int k = log2(r-l+1);	return min( st[l][k],st[r-(1<
      
       > n;	for(int i=1;i<=n;i++)	{
   		cin >> a[i];		if( a[i]=='(' )	pre[i] = pre[i-1]+1;			else	pre[i] = pre[i-1]-1;	}	for(int i=1;i<=n;i++)	{
   		pre[i] += base;		vec[pre[i]].push_back( i );	}	pre[0] = base;	SA(); init();	long long ANS = 0;	for(int i=1;i<=n;i++)	{
   		int now = sa[i];//按照sa的顺序加入 		int l = now+height[i], r = n, ans = 0;		while( r>=l )		{
   			int mid = l+r>>1;			if( get(now,mid)>=pre[now-1] )	l = mid+1, ans = mid;			else	r = mid-1; 		}		int las = pre[now-1];		if( ans==0 )	continue;		int x = upper_bound( vec[las].begin(),vec[las].end(),ans )-lower_bound( vec[las].begin(),vec[las].end(),now+height[i] );		ANS += x;	}	cout << ANS;}
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114868240 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！