#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
#define int long long
#define double long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int maxn=1e6+10,maxm=1e6+10,mod=1e9+7;
inline int read(){
	int c,w=0,n=0;
	while((c=getchar())<'0'||'9'<c) w=c=='-';
	do n=n*10+c-'0';while('0'<=(c=getchar())&&c<='9');
	return w?-n:n;
}
int write(int n){
	if(n<0) putchar('-'),n=-n;
	if(n>9) write(n/10);
	putchar(n%10+'0');
	return n;
}
inline int ksm(int x,int k,int mod=mod){
	int ans=1;
	for(;k;k>>=1,x=x*x%mod) if(k&1) ans=ans*x%mod;
	return ans;
}

int n,t[maxn],a[maxn],b[maxn],rkb[maxn],sa[maxn],rk[maxn];
int h,ans,height[maxn],st[maxn][21],nxt[maxn],lst[maxn];
string s;

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>s,n=s.size(),s=(char)0+s,height[0]=height[n+1]=-1;
	rep(i,1,n) t[s[i]]=1;
	rep(i,1,128) t[i]+=t[i-1];
	rep(i,1,n) rk[i]=t[s[i]-1]+1;
	for(int l=1;l<=n;l<<=1){
		rep(i,1,n) a[i]=rk[i],b[i]=i+l<=n?rk[i+l]:0;
		rep(i,0,n) t[i]=rkb[i]=0;
		rep(i,1,n) ++t[b[i]+1];
		rep(i,1,n) t[i]+=t[i-1];
		rep(i,1,n) rkb[++t[b[i]]]=i;
		rep(i,0,n) t[i]=0;
		rep(i,1,n) ++t[a[i]+1];
		rep(i,1,n) t[i]+=t[i-1];
		rep(i,1,n) sa[++t[a[rkb[i]]]]=rkb[i];
		rep(i,1,n) if(a[sa[i-1]]==a[sa[i]]&&b[sa[i-1]]==b[sa[i]]) rk[sa[i]]=rk[sa[i-1]];
		else rk[sa[i]]=i;
	}
	rep(i,1,n) if(rk[i]>1){
		for(int j=sa[rk[i]-1];max(i,j)+h<=n&&s[i+h]==s[j+h];++h);
		st[rk[i]-1][0]=height[rk[i]-1]=h,h=max(0ll,h-1);
	}
	per(i,n,1) for(nxt[i]=i+1;height[i]<height[nxt[i]];nxt[i]=nxt[nxt[i]]);
	rep(i,1,n) for(lst[i]=i-1;height[i]<=height[lst[i]];lst[i]=lst[lst[i]]);
	rep(i,1,n) ans+=2*(i-lst[i])*(nxt[i]-i)*height[i];
	cout<<n*(n-1)*(n+1)/2-ans;
	return 0;
}

其中，这两行代码

	per(i,n,1) for(nxt[i]=i+1;height[i]<height[nxt[i]];nxt[i]=nxt[nxt[i]]);
	rep(i,1,n) for(lst[i]=i-1;height[i]<=height[lst[i]];lst[i]=lst[lst[i]]);

改成

	per(i,n,1) for(nxt[i]=i+1;height[i]<=height[nxt[i]];nxt[i]=nxt[nxt[i]]);
	rep(i,1,n) for(lst[i]=i-1;height[i]<=height[lst[i]];lst[i]=lst[lst[i]]);

或

	per(i,n,1) for(nxt[i]=i+1;height[i]<height[nxt[i]];nxt[i]=nxt[nxt[i]]);
	rep(i,1,n) for(lst[i]=i-1;height[i]<height[lst[i]];lst[i]=lst[lst[i]]);

都不对，为什么改成最一边大于，一边小于那种就对了？