SA的题目
差异：https://lydsy.com/JudgeOnline/problem.php?id=3238
题意概述：给定一个长度为 $n$ 的字符串 $S$，令 $T_ i$ 表示它从第 $i$ 个字符开始的后缀。$2<=N<=50000$。求$$\sum_{1<=i<j<=n}len(T_i)+len(T_j)-2 \times lcp(T_i,T_j)$$
通过观察可以发现，每个后缀的长度被计算的次数是 $n-1$ ,而所有后缀长度的和是一个等差数列，$\frac{n\times(n+1)}{2}$，所以式子的前半部分就是 $\frac{(n^3-n)}{2}$ 。
现在来求后半部分，等价于所有后缀对的 $lcp$ 之和再乘二，看到后缀，我就想到 $SA$，看到 $lcp$ ，我就想到求 $height$ 数组，求出 $height$ 数组，原问题就转化为整个序列中（每个区间的最小值）之和。
这个问题可以用单调栈扫两遍，找到每个点可以作为最小值的左右端点，并注意一下边界情况，有相同最小值的时候不要算重复就可以通过了。
对于这种问题还有另一个很不错的方法：烜式合并；这是烜神仙的 $blog$ :https://www.cnblogs.com/asuldb/p/10205640.html
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string>
# define R register int
# define ll long long
using namespace std;
const int maxn=;
char c[maxn];
int n,sa[maxn],ht[maxn],ta[maxn],tb[maxn],A[maxn],B[maxn],rk[maxn],m,l[maxn],r[maxn],Tp,k[maxn],v[maxn];
ll ans,anss;
inline void build_SA()
{
for (R i=;i<=n;++i) ta[ c[i] ]++;
for (R i=;i<=;++i) ta[i]+=ta[i-];
for (R i=n;i>=;--i) sa[ ta[ c[i] ]-- ]=i;
rk[ sa[] ]=;
for (R i=;i<=n;++i) rk[ sa[i] ]=(c[ sa[i] ]==c[ sa[i-] ])?rk[ sa[i-] ]:rk[ sa[i-] ]+;
for (R l=;rk[ sa[n] ]<n;l<<=)
{
for (R i=;i<=n;++i) ta[i]=tb[i]=;
for (R i=;i<=n;++i)
{
ta[ A[i]=rk[i] ]++;
tb[ B[i]=(i+l<=n)?rk[i+l]: ]++;
}
for (R i=;i<=n;++i) ta[i]+=ta[i-],tb[i]+=tb[i-];
for (R i=n;i>=;--i) rk[ tb[ B[i] ]-- ]=i;
for (R i=n;i>=;--i) sa[ ta[ A[ rk[i] ] ]-- ]=rk[i];
rk[ sa[] ]=;
for (R i=;i<=n;++i)
{
rk[ sa[i] ]=rk[ sa[i-] ];
if(A[ sa[i] ]!=A[ sa[i-] ]||B[ sa[i] ]!=B[ sa[i-] ]) rk[ sa[i] ]++;
}
}
int j=;
for (R i=;i<=n;++i)
{
if(j) j--;
while (c[ i+j ]==c[ sa[ rk[i]- ]+j ]) j++;
ht[ rk[i] ]=j;
}
}
int main()
{
scanf("%s",c+);
n=strlen(c+);
ans=1LL*n*(n+)/*(n-);
build_SA();
for (R i=;i<=n;++i)
{
while(Tp&&ht[i]<v[Tp]) r[ k[Tp] ]=i-k[Tp],Tp--;
k[++Tp]=i,v[Tp]=ht[i];
}
for (R i=;i<=Tp;++i) r[ k[i] ]=n-k[i]+;
Tp=;
for (R i=n;i>=;--i)
{
while(Tp&&ht[i]<=v[Tp]) l[ k[Tp] ]=k[Tp]-i,Tp--;
k[++Tp]=i,v[Tp]=ht[i];
}
for (R i=;i<=Tp;++i) l[ k[i] ]=k[i]-;
for (R i=;i<=n;++i) anss+=1LL*l[i]*r[i]*ht[i];
printf("%lld",ans-anss*);
return ;
}
差异