( ext{Description})

( ext{Solution})

(len) 的答案显然是 (n*(n+1)/2*(n-1))，我们只用考虑后面的 ( ext{LCP})。

转化一下就是求任意两个后缀的 ( ext{LCP}) 之和，放到后缀数组上来说，就是任取 (1le i<jle n)，求一次 (min{h[k]},(min{rk[i],rk[j]}le kle max{rk[i],rk[j]}))，再将每次的答案相加（其中 (h[i]) 是后缀排序后第 (i) 位与第 (i-1) 位的 ( ext{LCP})，(rk[i]) 是编号为 (i) 的后缀的排名）。

再转化一下，我们发现这其实就是 (h) 数组中任取 (1le i<jle n)，求 (min{h[k]},(ile kle j))，再将每次的答案相加。

有一个经典的转化：我们可以固定位置 (pos)，求在 (pos) 左边第一个 (h) 小于 (h[pos]) 的 (L[pos])，在 (pos) 右边第一个 (h) 小于 (h[pos]) 的 (R[pos])。答案就是：

[sum_{i=1}^n h[i] imes (i-L[i]) imes (R[i]-i) ]

~~是不是哪里有点不对？~~

上面的转化是在保证没有元素相同，而且可以取 (i=j) 的情况。

而这道题的元素可以相同就有点难搞。

还有一个很经典的转化~~（为什么我全都不会啊喂）~~：可以人为给相同的元素按在数组的顺序赋优先级。

需要注意的是，(h[i]) 代表的是 (i) 与 (i-1) 的 ( ext{LCP})，就是表示的不是单点，所以之前统计的配对和是 ([L[i],i]) 与 ([i,R[i]])，而现在的配对和应该是 ([L[i],i-1]) 与 ([i,R[i]-1])（可以看个示意图）。

[1 2 3 ... L[i] ... i ... R[i] ]

[ 6 7 5 ]

第一排是下标，第二排是 (h) 值。

具体做法就是用单调栈维护单增与不减，注释会比较详细。

( ext{Code})

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

const int maxn=5e5+5;

char s[maxn];
int n,m='z',c[maxn],x[maxn],y[maxn],sa[maxn],num,rk[maxn],h[maxn],sta[maxn],tp,pre[maxn],suf[maxn];
ll ans;

void Suffix() {
	rep(i,1,n) ++c[x[i]=s[i]];
	rep(i,2,m) c[i]+=c[i-1];
	fep(i,n,1) sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1) {
		num=0;
		rep(i,n-k+1,n) y[++num]=i;
		rep(i,1,n) if(sa[i]>k) y[++num]=sa[i]-k;
		rep(i,1,m) c[i]=0;
		rep(i,1,n) ++c[x[i]];
		rep(i,2,m) c[i]+=c[i-1];
		fep(i,n,1) sa[c[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		x[sa[1]]=1; num=1;
		rep(i,2,n)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		m=num;
	}
}

void LCP() {
	int k=0;
	rep(i,1,n) rk[sa[i]]=i;
	rep(i,1,n) {
		if(rk[i]==1) continue;
		if(k) --k;
		int j=sa[rk[i]-1];
		while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;
		h[rk[i]]=k;
	}
}

int main() {
	scanf("%s",s+1); n=strlen(s+1);
	Suffix(); LCP();
	sta[0]=1;
	rep(i,2,n) { // 维护单增，如果前面有相等的就停在第一个相等的位置
		while(tp&&h[sta[tp]]>h[i]) --tp;
		++tp;
		pre[sta[tp]=i]=sta[tp-1];
	}
	sta[tp=0]=n+1;
	fep(i,n,1) { // 维护不减
		while(tp&&h[sta[tp]]>=h[i]) --tp;
		++tp;
		suf[sta[tp]=i]=sta[tp-1];
	}
	rep(i,1,n) ans+=1ll*h[i]*(i-pre[i])*(suf[i]-i);
	print(1ll*n*(n+1)/2*(n-1)-2ll*ans,'
');
	return 0;
}

( ext{Old Version})

((displaystyle sum^{}_{1<=i<j<=n}{i+j})-2*displaystyle sum^{}_{1<=i<j<=n}{lcp(suf(i),suf(j))})

(=(n-1)*Σi-2*displaystyle sum^{}_{1<=i<j<=n}{lcp(suf(i),suf(j))})

(=frac{(n-1)*(1+n)*n}{2}-2*displaystyle sum^{}_{1<=i<j<=n}{lcp(suf(i),suf(j))})

注意前者的(i)与(j)是转换了一下的，为了后面化简顺利。（也就是说前面的(i)与(j)与后面的(i)与(j)不是对应一样的）

我们就可以考虑后面的环节。因为暴枚的时间是(n)方，我们肯定过不去。所以只有用一个小一点的枚举。

可以利用(h)数组。因为两个后缀的(lcp)是排名在它们之间的串的(h)值的(min)。反过来思考，我们只要计算出以(i)为中心的(h)值比(h[i])大的连续区间的长度就行了。我们可以用单调栈维护。

统计出两边的个数后我们相乘就能得到(lcp)为(h[i])的区间个数了。

注意处理最后仍未被弹出栈的元素。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 5e5 + 3;

long long ans;
int cnt, l[N], r[N], s[N], lg[N], T, rmq[N][20], n, m, h[N], tax[N], SA[N], tp[N], rk[N], a[N];

int read() {
	int x = 0, f = 1; char S;
	while((S = getchar()) > '9' || S < '0') {
		if(S == '-') f = -1;
		if(S == EOF) exit(0);
	}
	while(S <= '9' && S >= '0') {
		x = (x << 1) + (x << 3) + (S ^ 48);
		S = getchar();
	}
	return x * f;
}

bool cmp(const int x, const int y, const int d) {return tp[x] == tp[y] && tp[x + d] == tp[y + d];}

void Sort() {
    for(int i = 0; i <= m; ++ i) tax[i] = 0;
    for(int i = 1; i <= n; ++ i) ++ tax[rk[tp[i]]];
    for(int i = 1; i <= m; ++ i) tax[i] += tax[i - 1];
    for(int i = n; i >= 1; -- i) SA[tax[rk[tp[i]]] --] = tp[i];
}

void Swap(int &x, int &y) {
    x ^= y ^= x ^= y;
}

int Min(const int x, const int y) {
    if(x < y) return x;
    return y;
}

void Suffix() {
    for(int i = 1; i <= n; ++ i) rk[i] = a[i], tp[i] = i;
    m = 122; Sort();
    for(int w = 1, p = 1, i; p < n; m = p, w <<= 1) {
        for(p = 0, i = n - w + 1; i <= n; ++ i) tp[++ p] = i;
        for(i = 1; i <= n; ++ i) if(SA[i] > w) tp[++ p] = SA[i] - w;
        Sort(); swap(rk, tp); rk[SA[1]] = p = 1;
        for(i = 2; i <= n; ++ i) rk[SA[i]] = cmp(SA[i], SA[i - 1], w) ? p : ++ p;
    }
    int j, k = 0;
    for(int i = 1; i <= n; h[rk[i ++]] = k)
        for(k = k ? k - 1 : k, j = SA[rk[i] - 1]; a[i + k] == a[j + k]; ++ k);
    for(int i = 1; i <= n; ++ i) rmq[i][0] = h[i];
    for(int j = 1; (1 << j) <= n; ++ j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++ i)
            rmq[i][j] = Min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
}

int lcp(const int x, const int y) {
    int l = rk[x], r = rk[y];
    if(l > r) Swap(l, r);
    int t = lg[r - l];
    return Min(rmq[l + 1][t], rmq[r - (1 << t) + 1][t]);
}

int main() {
    char ch[N];
    scanf("%s", ch); n = strlen(ch);
    for(int i = 1; i <= n; ++ i) a[i] = ch[i - 1];
    Suffix();
    ans = 1ll * n * (n - 1) * (n + 1) / 2;
    s[cnt = 1] = 1;
    for(int i = 2; i <= n; ++ i) {
        while(cnt && h[s[cnt]] > h[i]) r[s[cnt --]] = i;
        l[i] = s[cnt];
        s[++ cnt] = i;
    }
    while(cnt) r[s[cnt --]] = n + 1;
    for(int i = 2; i <= n; ++ i)
        ans -= 2ll * (i - l[i]) * (r[i] - i) * h[i];
    printf("%lld
", ans);
    return 0;
}