bzoj千题计划314:bzoj3238: [Ahoi2013]差异(后缀数组+st表+单调栈)

https://www.lydsy.com/JudgeOnline/problem.php?id=3238

跟 bzoj3879 差不多

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 500001 int n,m,mm;
char s[N];
int a[N]; int v[N];
int p,q=,k;
int sa[][N],rk[][N]; int h[N];
int st[N][]; int Log[N]; int ST[N],top;
int num[N],val[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void mul(int *sa,int *rk,int *SA,int *RK)
{
for(int i=;i<=n;++i) v[rk[sa[i]]]=i;
for(int i=n;i;--i) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;
for(int i=n-k+;i<=n;++i) SA[v[rk[i]]--]=i;
for(int i=;i<=n;++i) RK[SA[i]]=RK[SA[i-]]+(rk[SA[i]]!=rk[SA[i-]] || rk[SA[i]+k]!=rk[SA[i-]+k]);
} void presa()
{
for(int i=;i<=n;++i) v[a[i]]++;
for(int i=;i<=;++i) v[i]+=v[i-];
for(int i=;i<=n;++i) sa[p][v[a[i]]--]=i;
for(int i=;i<=n;++i) rk[p][sa[p][i]]=rk[p][sa[p][i-]]+(a[sa[p][i]]!=a[sa[p][i-]]);
for(k=;k<n;k<<=,swap(p,q)) mul(sa[p],rk[p],sa[q],rk[q]);
} void get_height()
{
int k=,j;
for(int i=;i<=n;++i)
{
j=sa[p][rk[p][i]-];
while(a[i+k]==a[j+k]) k++;
h[rk[p][i]]=k;
if(k) k--;
}
} void prest()
{
for(int i=;i<=n;++i) st[i][]=h[i];
for(int i=,k=;i<=;++i,k<<=)
for(int j=;j+k-<=n;++j)
st[j][i]=min(st[j][i-],st[j+k/][i-]);
} int get(int i,int j)
{
i++;
int l=Log[j-i+];
return min(st[i][l],st[j-(<<l)+][l]);
} void solve()
{
top=;
int tmp_num;
long long now=,ans=;
for(int i=;i<=n;++i)
{
tmp_num=;
while(top && h[i]<=h[ST[top]])
{
now-=1LL*num[top]*val[top];
tmp_num+=num[top--];
}
tmp_num++;
ST[++top]=i;
num[top]=tmp_num;
val[top]=h[i];
now+=1LL*tmp_num*h[i];
ans+=now;
}
ans=-ans*;
ans+=1LL*n*(n+)/*(n-);
cout<<ans<<'\n';
} int main()
{
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;++i) Log[i]=Log[i>>]+;
for(int i=;i<=n;++i) a[i]=s[i]-'a'+;
presa();
get_height();
prest();
solve();
}
上一篇:BZOJ 4453: cys就是要拿英魂![后缀数组 ST表 单调栈类似物]


下一篇:POJ 3261 可重叠的 k 次最长重复子串【后缀数组】