一行，一个字符串S

一行，一个整数，表示所求值

2<=N<=500000,S由小写英文字母组成

#include<map>#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define inf 1000000007#define ll long long#define N 500010int v[N],rk1[N],rk2[N],sa1[N],sa2[N],n,a[N],ht[N];int l[N],r[N],q[N],tot;int *sa=sa1,*SA=sa2,*rk=rk1,*RK=rk2;char s[N];ll ans;int main(){    scanf("%s",s+1);    n=strlen(s+1);    for(int i=1;i<=n;i++){a[i]=s[i]-‘a‘+1;v[a[i]]++;}    for(int i=1;i<=30;i++) v[i]+=v[i-1];    for(int i=n;i;i--) sa[v[a[i]]--]=i;    for(int i=1;i<=n;i++) rk[sa[i]]=rk[sa[i-1]]+(a[sa[i]]!=a[sa[i-1]]);    for(int k=1;k<=n;k<<=1)    {        for(int i=1;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+1;i<=n;i++) SA[v[rk[i]]--]=i;        for(int i=1;i<=n;i++) RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);        swap(sa,SA);swap(rk,RK);    }    int k=0,j;    for(int i=1;i<n;i++)    {        j=sa[rk[i]-1];        while(s[i+k]==s[j+k]) k++;        ht[rk[i]]=k;        if(k) k--;    }    ht[0]=-inf;    for(int i=1;i<=n;i++)    {        while(ht[i]<=ht[q[tot]]) tot--;        l[i]=q[tot]+1; q[++tot]=i;    }    ht[n+1]=-inf;tot=0;q[0]=n+1;    for(int i=n;i;i--)    {        while(ht[i]<ht[q[tot]]) tot--;        r[i]=q[tot]-1; q[++tot]=i;    }    ans=(ll)(n+1)*n*(n-1)/2;    for(int i=1;i<=n;i++) ans-=2LL*(i-l[i]+1)*(r[i]-i+1)*ht[i];    printf("%lld\n",ans);    return 0;}