思路

暴力拆贡献。

$$\\ ans={n(n-1)(n+1)\over2}-2\sum_{i<j}\operatorname{lcp}(i,j) \\={n(n-1)(n+1)\over2}-2\sum_{i\le j}\min(H,[i,j]) \\ $$

大力在 H 数组上跑笛卡尔树即可。

Code

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace SUF_ARRAY
{
    struct ST
    {
        typedef std::vector<uint>vec;
        vec Log2;std::vector<vec>Val;
        voi bzr(){Val.clear(),Log2.clear();}
        voi build(vec A)
        {
            uint n=A.size();bzr(),Val.push_back(A),Log2.resize(n+1);
            Log2[0]=-1u;for(uint i=1;i<=n;i++)Log2[i]=Log2[i>>1]+1;
            for(uint len=2,dep=1;len<=n;len<<=1,dep++)
            {
                Val.push_back(vec(n-len+1));for(uint i=0;i+len<=n;i++)Val[dep][i]=std::min(Val[dep-1][i],Val[dep-1][i+(len>>1)]);
            }
        }
        uint find(uint l,uint r){uint dep=Log2[r-l];return std::min(Val[dep][l],Val[dep][r-(1u<<dep)]);}
    };
    template<typename T>
    class SufArray
    {
        private:
            typedef std::vector<uint>vec;vec rk,sa,h;ST p;
        public:
            voi bzr(){rk.clear(),sa.clear(),h.clear(),p.bzr();}
            voi build(std::vector<T>User,bol op=true)
            {
                uint n=User.size();bzr();if(!n)return;
                rk.resize(n),sa.resize(n),h.resize(n);
                {
                    typedef std::pair<T,uint>Pair;
                    std::vector<Pair>q(n);
                    for(uint i=0;i<n;i++)q[i]=Pair(User[i],i);
                    std::sort(q.begin(),q.end());
                    rk[q[0].second]=0;for(uint i=1;i<n;i++)rk[q[i].second]=(q[i].first==q[i-1].first)?rk[q[i-1].second]:i;
                }
                {
                    typedef std::pair<uint,uint>Pair;
                    typedef std::pair<Pair,uint>Pair2;
                    std::vector<Pair2>q(n),tmp(n);
                    for(uint dep=1;dep<n;dep<<=1)
                    {
                        for(uint i=0;i<n;i++)q[i]=Pair2(Pair(rk[i],(i+dep<n)?rk[i+dep]+1:0),i);
                        {
                            vec cnt(n+1);
                            for(uint i=0;i<n;i++)cnt[q[i].first.second]++;
                            for(uint i=0;i<n;i++)cnt[i+1]+=cnt[i];
                            for(uint i=0;i<n;i++)tmp[--cnt[q[i].first.second]]=q[i];
                        }
                        {
                            vec cnt(n);
                            for(uint i=0;i<n;i++)cnt[tmp[i].first.first]++;
                            for(uint i=1;i<n;i++)cnt[i]+=cnt[i-1];
                            for(uint i=n-1;i+1;i--)q[--cnt[tmp[i].first.first]]=tmp[i];
                        }
                        rk[q[0].second]=0;for(uint i=1;i<n;i++)rk[q[i].second]=(q[i].first==q[i-1].first)?rk[q[i-1].second]:i;
                    }
                }
                for(uint i=0;i<n;i++)sa[rk[i]]=i;
                for(uint i=0,k=0;i<n;i++)
                {
                    if(k)k--;
                    if(rk[i])
                    {
                        for(uint j=sa[rk[i]-1];i+k<n&&j+k<n&&User[i+k]==User[j+k];k++);
                        h[rk[i]]=k;
                    }
                }
                if(op)lcp_ready();
            }
            voi build(T*User,uint n,bol op=true){
                std::vector<T>QAQ(n);for(uint i=0;i<n;i++)QAQ[i]=User[i];
                build(QAQ,op);
            }
            voi lcp_ready(){p.build(h);}
            uint size(){return sa.size();}
            uint rank(uint num){return rk[num];}
            uint SA(uint num){return sa[num];}
            uint height(uint num){return h[num];}
            uint lcp(uint a,uint b){return(a==b)?size()-a:(rk[a]<rk[b]?p.find(rk[a]+1,rk[b]+1):p.find(rk[b]+1,rk[a]+1));}
            uint lcp2(uint l,uint r){return(l+1==r)?size()-sa[l]:p.find(l+1,r);}
    };
}
using namespace SUF_ARRAY;
typedef SufArray<chr>SA;
chr C[500005];SA S;
struct node{node*L,*R;uint l,r;}N[500005];
uint H[500005];
#define ID(p) ((p)-N)
ullt dfs(node*qaq)
{
    ullt ans=0;
    if(qaq->L!=NULL)ans+=dfs(qaq->L),qaq->l=qaq->L->l;else qaq->l=ID(qaq);
    if(qaq->R!=NULL)ans+=dfs(qaq->R),qaq->r=qaq->R->r;else qaq->r=ID(qaq);
    ans+=(ullt)H[ID(qaq)]*(ID(qaq)-qaq->l+1)*(qaq->r-ID(qaq)+1);
    return ans;
};
int main()
{
    scanf("%s",C);uint n;for(n=0;C[n];n++);
    ullt ans=(ullt)n*(n-1)*(n+1)/2;
    S.build(C,n,0);for(uint i=0;i<n;i++)H[i]=S.height(i);
    std::vector<node*>User;
    for(uint i=0;i<n;i++)
    {
        node*now=NULL;
        while(!User.empty()&&H[ID(User.back())]>=H[i])
        {
            User.back()->R=now;
            now=User.back();
            User.pop_back();
        }
        N[i].L=now;
        User.push_back(N+i);
    }
    node*now=NULL;
    while(User.size())User.back()->R=now,now=User.back(),User.pop_back();
    ans-=dfs(now)*2;
    printf("%llu\n",ans);
    return 0;
}