rt
莫名其妙的85分,第12、13、15个点WA了,求各位大佬帮忙看一下是哪里错了,谢谢!
题目描述:P4248 差异 做法是常规的SA+单调栈(码风惊奇,大佬勿喷)
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500010;
int n;
char s[MAXN];
int sa[MAXN],h[MAXN],a[MAXN],x[MAXN*2],y[MAXN*2];
int rk[MAXN];
inline void SA()
{
int m=128;
for(register int i=0;i<n;++i) ++a[x[i]=s[i]];
for(register int i=1;i<=m;++i) a[i]+=a[i-1];
for(register int i=n-1;i>=0;--i) sa[--a[x[i]]]=i;
for(register int k=1;k<=n;k<<=1)
{
register int num=0;
for(register int i=n-k;i<n;++i) y[num++]=i;
for(register int i=0;i<n;++i)
if(sa[i]>=k) y[num++]=sa[i]-k;
for(register int i=0;i<=m;++i) a[i]=0;
for(register int i=0;i<n;++i) ++a[x[y[i]]];
for(register int i=1;i<=m;++i) a[i]+=a[i-1];
for(register int i=n-1;i>=0;--i) sa[--a[x[y[i]]]]=y[i];
swap(x,y),num=0;
x[sa[0]]=0;
for(register int i=1;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==m) return;
m=num;
}
}
inline void geth()
{
register int k=0;
for(register int i=0;i<n;++i) rk[sa[i]]=i;
for(register int i=0;i<n;++i)
{
if(!rk[i]) continue;
if(k) --k;
register int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) ++k;
h[rk[i]]=k;
}
}
long long ans=0;
int st[MAXN],tp=0;
long long f[MAXN];
int pos=0;
int main()
{
scanf("%s",s);
n=strlen(s);
SA(),geth();
ans=1ll*n*(n+1)/2*(n-1);
for(register int i=0;i<n;++i)
{
while(tp&&h[st[tp]]>h[i]) --tp;
if(tp) f[i]=0ll+f[st[tp]]+1ll*(i-st[tp])*h[i];
else f[i]=0ll+f[pos]+1ll*(i-pos)*h[i];
if(h[i]==0) pos=i;
ans-=2ll*f[i];
st[++tp]=i;
}
printf("%lld\n",ans);
}