希望更丰富的展现?使用Markdown
by xsI666 @ 2019-01-18 11:30:35
```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
#define N 500030
char ch[N];
int x[N],y[N],c[N],sa[N],rk[N];
ll hei[N],n;
int m;
ll ans,totallen;
ll s[N],cnt[N];
int tot;
inline void getsa()
{
for(int i=1;i<=n;i++)x[i]=ch[i],m=max(m,x[i]);
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;i--)sa[c[x[i]]--]=i;
int k=1;
while(k<=n)
{
int js=0;
for(int i=n-k+1;i<=n;i++)y[++js]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++js]=sa[i]-k;
memset(c,0,sizeof(c));
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;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
js=0;
x[sa[1]]=++js;
for(int i=1;i<=n;i++)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=js;
else x[sa[i]]=++js;
}
m=js;
if(m==n)break;
k<<=1;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
}
inline void gethei()
{
ll k=0;
for(int i=1;i<=n;i++)
{
if(rk[i]==1)hei[rk[i]]=0;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&ch[i+k]==ch[j+k])k++;
hei[rk[i]]=k;
}
}
int main()
{
scanf("%s",ch+1);
n=strlen(ch+1);
getsa();
gethei();
ans=hei[2];
s[++tot]=hei[2];
cnt[tot]=1ll;
ll sum=ans;
for(int i=3;i<=n;i++)
{
ll tcn=1ll;
while(tot>0&&s[tot]>=hei[i])
{
sum-=s[tot]*cnt[tot];
tcn+=cnt[tot];
tot--;
}
s[++tot]=hei[i];
cnt[tot]=tcn;
sum+=s[tot]*cnt[tot];
ans+=sum;
}
ll tn=1ll*n;
totallen=1ll*(tn-1ll)*tn*(tn+1ll)/2ll;
printf("%lld\n",totallen-2ll*ans);
}
```
by LebronDurant @ 2019-01-18 11:40:04
第四个点WA
by LebronDurant @ 2019-01-18 13:09:17