BZOJ3238 [Ahoi2013]差异 SA+单调栈

题面

题解

考虑把要求的那个东西拆开算，前面一个东西像想怎么算怎么算，后面那个东西在建出\(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);

}