题面
题解
考虑把要求的那个东西拆开算，前面一个东西像想怎么算怎么算，后面那个东西在建出\(height\)数组后相当于是求所有区间\(min\)的和*2，单调栈维护一波即可。
#include<bits/stdc++.h>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define cross(i,k) for (int i=first[k];i;i=last[i])
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int N = 500010;
int n;
ll ans;
char c[N];
int cnt[N],x[N],y[N],SA[N],Rank[N],height[N];
inline void Radix_Sort(){
int Max=0;
For(i,1,n) cnt[x[i]]++,Max=max(Max,x[i]);
For(i,1,Max) cnt[i]+=cnt[i-1];
Dow(i,n,1) SA[cnt[x[y[i]]]--]=y[i];
For(i,1,Max) cnt[i]=0;
}
inline void GetSA(){
For(i,1,n) x[i]=c[i],y[i]=i;
Radix_Sort();
for (int i=1,p=1;p<n;i<<=1){
p=0;
For(j,n-i+1,n) y[++p]=j;
For(j,1,n) if (SA[j]>i) y[++p]=SA[j]-i;
Radix_Sort(),swap(x,y),x[SA[1]]=p=1;
For(j,2,n) x[SA[j]]=(y[SA[j]]==y[SA[j-1]]&&y[SA[j]+i]==y[SA[j-1]+i])?p:++p;
}
For(i,1,n) Rank[SA[i]]=i;
int k=0;
For(i,1,n){
if (Rank[i]==1) continue;k=max(0,k-1);
for (int j=SA[Rank[i]-1];j+k<=n&&i+k<=n&&c[j+k]==c[i+k];k++);
height[Rank[i]]=k;
}
}
int top,q[N],l[N],r[N];
inline ll SumLcp(){
For(i,1,n){
while (top&&height[i]<height[q[top]]) r[q[top--]]=i-1;
q[++top]=i,l[i]=q[top-1]+1;
}
while (top) r[q[top--]]=n;
ll ans=0;
For(i,1,n) ans+=1ll*(r[i]-i+1)*(i-l[i]+1)*height[i];
return ans;
}
int main(){
scanf("%s",c+1),n=strlen(c+1);
GetSA();
For(i,1,n) ans+=1ll*(n-i+1)*(n-i)+1ll*(n-i)*(n-i+1)/2;
printf("%lld",ans-SumLcp()*2);
}