题意
给定一个长度为\(n\)的字符串\(s\)，设对于两字符串\(x\)，\(y\)，\(f(x,y)=\max\{k|1\le k\le \min(|x|,|y|)且\forall i\in [1,k]\cap N^*,x_i=y_i\}\)。
设\(S_i={s_is_{i+1}\cdots s_n}\)。对于每一个\(k\in [1,n]\cap N^*\)，求\(\sum_{i=1}^nf(S_i,S_k)\)。
思路
首先预处理出\(height\)数组，\(h[i]=lcp(suf_{sa_i},suf_{sa_{i-1}})\)。
有结论：\(lcp(suf_i,suf_j)(rnk_i<rnk_j)=\min_{k=rnk_i+1}^{rnk_j}h_k\)。
此时，题目转换为：给出一长度为\(n\)的序列\(a_1,a_2,\cdots,a_n\)，要求对每一个\(i\)求出\(\sum_{i=1}^n\min_{k=\min(i,j)}^{\max(i,j)}a_k\)。
这个问题可以用单调栈轻松求出。
总时间复杂度：\(O(n+SA(n))\)，其中\(SA(n)\)表示求后缀数组所需要的时间。
代码
using namespace std;
typedef long long ll;
const int mod=998244353;
int fir[2000005],rnk[2000005],sa[2000005],sec[2000005],s[2000005],h[2000005];
int st[2000005],top;
ll val[2000005],ans[2000005];
char str[2000005];
void MakeSA(int n,int m){
int *x=rnk,*y=sec;
for(int i=1;i<=n;i++)s[x[i]=str[i]-‘a‘+1]++;
for(int i=1;i<=m;i++)s[i]+=s[i-1];
for(int i=n;i;i--)sa[s[x[i]]--]=i;
for(int j=1,p=0;p<n?(p=0,1):0;j<<=1,m=p){
for(int i=n-j+1;i<=n;i++)y[++p]=i;
for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
for(int i=1;i<=m;i++)s[i]=0;
for(int i=1;i<=n;i++)s[fir[i]=x[y[i]]]++;
for(int i=1;i<=m;i++)s[i]+=s[i-1];
for(int i=n;i;i--)sa[s[fir[i]]--]=y[i];
swap(x,y),x[sa[p=1]]=1;
for(int i=2;i<=n;i++)x[sa[i]]=(p+=(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+j]!=y[sa[i-1]+j]));
}
for(int i=1;i<=n;i++)rnk[sa[i]]=i;
for(int i=1,j=0;i<=n;i++){
if(rnk[i]==1)h[rnk[i]]=0;
else {
j=max(j-1,0);
while(str[i+j]==str[sa[rnk[i]-1]+j])j++;
h[rnk[i]]=j;
}
}
top=0,st[0]=1;
for(int i=2;i<=n;i++){
while(top&&h[st[top]]>=h[i])top--;
st[++top]=i,val[top]=val[top-1]+1ll*(i-st[top-1])*h[i];
ans[i]+=val[top];
}
top=0,st[0]=n+1;
for(int i=n;i>=2;i--){
while(top&&h[st[top]]>=h[i])top--;
st[++top]=i,val[top]=val[top-1]+1ll*(st[top-1]-i)*h[i];
ans[i-1]+=val[top];
}
for(int i=1;i<=n;i++)printf("%lld\n",ans[rnk[i]]+(n-i+1));
}
int main(){
int n;
cin>>n>>str+1;
MakeSA(n,26);
}