题解 CF653F 【Paper task】
Durant_Lee
2019-02-28 08:34:36
[欢迎来我的blog逛逛~](https://blog.csdn.net/Dream_Lolita/article/details/88010611)
【题目】
给定一个括号串，问有多少种不同的合法括号子串。$n\leq 5\times 10^5$
【解题思路】
首先我们将左括号看作$1$，右括号看作$-1$，肯定要处理出一个前缀和数组。
如果不考虑重复，那么我们不妨考虑求以每个位置开头的合法子串个数，即对于每个位置$i$，我们需要求有多少个
$$i<j\leq n,\text{s.t.} s_j=s_{i-1},\forall i\leq k \leq j ,s_k\geq s_{i-1}$$
这个问题我们可以先处理出每种前缀和的所有位置，并通过$\text{RMQ}$维护区间最小值，然后在之前处理出的位置数组中二分判断最大可选的$j$在哪个位置即可。
现在要求去重，我们可以求出$height$数组，然后$j$的可选范围就是
$$sa_i+height_i+1\leq j\leq n$$
除此之外的做法都是一样的。
复杂度$O(n\log n)$
【参考代码】
```cpp
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e6+10,M=500001;
namespace SA
{
int sa[N],rk[N],hi[N];
int wa[N],wb[N],wx[N],wy[N];
bool cmp(int *r,int a,int b,int l){return r[a]==r[b] && r[a+l]==r[b+l];}
void getsa(int *r,int n,int m)
{
int *x=wa,*y=wb,*t,i,j,p;
for(i=0;i<m;++i) wx[i]=0;
for(i=0;i<n;++i) wx[x[i]=r[i]]++;
for(i=1;i<m;++i) wx[i]+=wx[i-1];
for(i=n-1;~i;--i) sa[--wx[x[i]]]=i;
for(j=1,p=0;p<n;j<<=1,m=p)
{
for(p=0,i=n-j;i<n;++i) y[p++]=i;
for(i=0;i<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<m;++i) wx[i]=0;
for(i=0;i<n;++i) wx[wy[i]=x[y[i]]]++;
for(i=1;i<m;++i) wx[i]+=wx[i-1];
for(i=n-1;~i;--i) sa[--wx[wy[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;++i)
x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
}
}
void getheight(int *r,int n)
{
int i,j,k=0;
for(i=1;i<=n;++i) rk[sa[i]]=i;
for(i=0;i<n;hi[rk[i++]]=k)
for(k?--k:0,j=sa[rk[i]-1];r[i+k]==r[j+k];++k);
}
void adjust(int n)
{
for(int i=n;i;--i) ++sa[i],rk[i]=rk[i-1];
sa[0]=rk[0]=0;
}
void output(int n)
{
for(int i=0;i<=n;++i) printf("%d ",sa[i]); puts("");
for(int i=0;i<=n;++i) printf("%d ",rk[i]); puts("");
for(int i=0;i<=n;++i) printf("%d ",hi[i]); puts("");
}
void buildsa(int *r,int n,int m)
{
getsa(r,n+1,m);getheight(r,n);adjust(n);
}
}
using namespace SA;
namespace DreamLolita
{
ll ans;
int n,s[N],Log[N],fc[25],h[20][N],sum[N];
char ch[N];
vector<int>vec[N];
void initrmq(int n)
{
for(int i=n;i;--i) s[i]=s[i-1],sum[i]=sum[i-1]; s[0]=0;sum[0]=M;
for(int i=1;i<=n;++i) vec[sum[i]].pb(i);
fc[0]=1;for(int i=1;i<22;++i)fc[i]=fc[i-1]<<1;
for(int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;++i) h[0][i]=sum[i];
for(int j=1;j<20;++j) for(int i=1;i+fc[j]-1<=n;++i)
h[j][i]=min(h[j-1][i],h[j-1][i+fc[j-1]]);
}
int query(int l,int r)
{
if(l>r) swap(l,r);
int t=Log[r-l+1];
return min(h[t][l],h[t][r-fc[t]+1]);
}
void solution()
{
scanf("%d%s",&n,ch);
for(int i=0;i<n;++i) ch[i]=='('?(s[i]=sum[i]=1):(s[i]=2,sum[i]=-1);
for(int i=1;i<n;++i) sum[i]+=sum[i-1];
for(int i=0;i<n;++i) sum[i]+=M;
buildsa(s,n,N);initrmq(n);
for(int i=1;i<=n;++i)
{
int x=sa[i];
if(s[x]==2) continue;
int l=x+hi[i],r=n,res=l-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(query(x,mid)>=sum[x-1]) l=mid+1,res=mid;
else r=mid-1;
}
int t=sum[x-1];
ans+=upper_bound(vec[t].begin(),vec[t].end(),res)-lower_bound(vec[t].begin(),vec[t].end(),x+hi[i]);
}//wrong because x+hi[i]->res
printf("%lld\n",ans);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("CF653F.in","r",stdin);
freopen("CF653F.out","w",stdout);
#endif
DreamLolita::solution();
return 0;
}
```