后缀数组：

1、差异：
卡在两个地方。
1是相等的值可能多算或者漏算。要手模一下。相等的不能简单覆盖，记在一个上面。x==y,idx<idy，L和id不同。y的L应该记为idx+1,
否则会多算，重复。所以单调栈是<=。
2是L，R的计算。(i-id[top])之前写的是i-id+1.
性质：排名为 i, j(i < j) 的后缀的 lcp 为 min{height[k] | i + 1 ≤ k ≤ j}
sigma(leni,j)=(n-1)*(n+1)*n/2. n-1是每一个都被算了n-1次。后面是前缀和。
转换：求lcp。求heigh[i]成为最小值的区间。
    单调栈维护。小难点是相等的值要手模一下。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define forb(i,a,b) for(register int i=a;i>=b;--i)
#define il inline
#define LL long long
#define rg register
#define pf(a) printf("%d ",a)
#define PF(a) printf("%lld ",a)
#define phn puts("")
using namespace std;
int read();
/*
卡在两个地方。
1是相等的值可能多算或者漏算。要手模一下。相等的不能简单覆盖，记在一个上面。x==y,idx<idy，L和id不同。y的L应该记为idx+1,
否则会多算，重复。所以单调栈是<=。
2是L，R的计算。(i-id[top])之前写的是i-id+1.
性质：排名为 i, j(i < j) 的后缀的 lcp 为 min{height[k] | i + 1 ≤ k ≤ j}
sigma(leni,j)=(n-1)*(n+1)*n/2. n-1是每一个都被算了n-1次。后面是前缀和。
转换：求lcp。求heigh[i]成为最小值的区间。
    单调栈维护。小难点是相等的值要手模一下。
*/
#define NX 500010
int n,m;
char str[NX];
int a[NX],sa[NX],height[NX],rk[NX],tax[NX],tp[NX];
void Rsort(){
    F(i,0,m)tax[i]=0;
    F(i,1,n)++tax[rk[tp[i]]];
    F(i,1,m)tax[i]+=tax[i-1];
    forb(i,n,1)sa[tax[rk[tp[i]]]--]=tp[i];
}
int cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
void Suffix(){
    F(i,1,n)rk[i]=a[i],tp[i]=i;
    m=127;Rsort();
    for(int w=1,p=1,i;p<n;w<<=1,m=p){
        for(p=0,i=n-w+1;i<=n;++i)tp[++p]=i;
        F(i,1,n)if(sa[i]>w)tp[++p]=sa[i]-w;
        Rsort();swap(rk,tp);rk[sa[1]]=p=1;
        F(i,2,n)rk[sa[i]]=cmp(tp,sa[i],sa[i-1],w)?p:++p;
    }
    int j,k=0;
    for(int i=1;i<=n;height[rk[i++]]=k)
        for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
}
int sta[NX],id[NX],bg[NX],top;
int main(){
    scanf("%s",str+1);
    n=strlen(str+1);
    F(i,1,n)a[i]=str[i];
    Suffix();
    LL ans=1ll*(n-1)*(n+1)*n/2;
  //  F(i,1,n)pf(rk[i]);phn;
  //  F(i,1,n)pf(height[i]);phn;
    height[n+1]=-1;
  //  PF(ans);
    F(i,1,n+1){
        while(top&&sta[top]>height[i]){
            ans-=2ll*(id[top]-bg[top])*(i-id[top])*sta[top--];//PF(ans);
        }
        if(!top){
            sta[++top]=height[i];id[top]=i;bg[top]=0;
        }
        else{
        //    if(sta[top]!=height[i]){
               sta[++top]=height[i];id[top]=i;bg[top]=id[top-1];
        //    }
        }
    }
    printf("%lld",ans);
}
il int read(){
    rg int s=0,f=0;rg char ch;
    while(ch=getchar(),ch=='-'?f=1:0,ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9'){
        s=s*10+(ch^48);ch=getchar();
    }
    return s;
}
/*
g++ 1.cpp -g
./a.out
eededeedeedeedde

*/