题面
https://www.luogu.com.cn/problem/P4248
求一个字符串的 $\sum_{1\leq i
分析
前面的加法显然可以提出来为 $\frac{(n-1)n(n+1)}{2}$
那么就要求 $\sum_{1\leq i
LCP的话就用后缀数组求出height,转化为 $\sum_{1\leq i
就转化为了求所有区间的区间最小值和,单调栈结束本题
代码
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=5e5+10;
int n,sa[N],rk[N],height[N],c[N],x[N],y[N],stk[N],top,l[N],r[N];
ll ans;
char s[N];
void Suffix_Array(int n,char *s,int *sa,int *rk) {
int m='z',cnt;
for (int i=0;i<=m;i++) c[i]=0;
for (int i=1;i<=n;i++) c[x[i]=s[i]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i;i--) sa[c[x[i]]--]=i;
for (int j=1;j<=n;j<<=1) {
cnt=0;
for (int i=n-j+1;i<=n;i++) y[++cnt]=i;
for (int i=1;i<=n;i++) if (sa[i]-j>0) y[++cnt]=sa[i]-j;
for (int i=0;i<=m;i++) c[i]=0;
for (int i=1;i<=n;i++) c[x[i]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);x[sa[1]]=cnt=1;
for (int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[min(sa[i]+j,n+1)]==y[min(sa[i-1]+j,n+1)])?cnt:++cnt;
m=cnt;if (n==m) break;
}
for (int i=1;i<=n;i++) rk[sa[i]]=i;
}
void Get_Height(int n,char *s,int *sa,int *rk,int *height) {
int z=0;
for (int i=1;i<=n;i++) {
if (rk[i]==1) {height[1]=0;continue;}
if (z) z--;
while (i+z<=n&&sa[rk[i]-1]+z<=n&&s[i+z]==s[sa[rk[i]-1]+z]) z++;
height[rk[i]]=z;
}
}
int main() {
scanf("%s",s+1);n=strlen(s+1);
for (int i=1;i<=n;i++) ans+=1ll*(n-1)*(n-i+1);
Suffix_Array(n,s,sa,rk);Get_Height(n,s,sa,rk,height);
l[1]=stk[++top]=1;
for (int i=2;i<=n;i++) {
while (top&&height[stk[top]]>height[i]) r[stk[top--]]=i;
l[i]=stk[top];stk[++top]=i;
}
while (top) r[stk[top--]]=n+1;
for (int i=1;i<=n;i++) ans-=2ll*(r[i]-i)*(i-l[i])*height[i];
printf("%lld\n",ans);
}