[后缀数组][单调栈]luogu P4248 [AHOI2013]差异

题面

https://www.luogu.com.cn/problem/P4248

求一个字符串的 $sum_{1leq i<j leq n} n-i+1+n-j+1-2 imes LCP(s_{i..n},s_{j..n})$

分析

前面的加法显然可以提出来为 $frac{(n-1)n(n+1)}{2}$

那么就要求 $sum_{1leq i<j leq n} LCP(s_{i..n},s_{j..n})$

LCP的话就用后缀数组求出height，转化为 $sum_{1leq i<j leq n} min_{k=i+1}^{j} height_k$

就转化为了求所有区间的区间最小值和，单调栈结束本题

代码

#include <iostream>
#include <cstdio>
#include <cstring>
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
",ans);
}