BZOJ-3238: [Ahoi2013]差异

Description

n<=5*10^5

后缀树
正串的后缀自动机的pre树即为反串的后缀树。
对于反串建后缀自动机，在正串的后缀树上进行树形DP，lcp即为后缀树上两点的lca表示的串，在lca处统计代价即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501000 
typedef long long ll;
char s[N];
int n,last=1,tot=1,ch[N<<1][26],pre[N<<1],dep[N<<1],siz[N<<1];
void insert(int x)
{
    int p=last,cur=++tot;
    last=cur,dep[cur]=dep[p]+1,siz[cur]=1;
    for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
    if(!p) pre[cur]=1;
    else
    {
        int q=ch[p][x];
        if(dep[q]==dep[p]+1) pre[cur]=q;
        else
        {
            int clo=++tot;
            memcpy(ch[clo],ch[q],sizeof(ch[q]));
            dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
            for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
        }
    }
}
int main()
{
    scanf("%s",s),n=strlen(s);
    int i; ll ans=0;
    for(i=n-1;i>=0;--i) insert(s[i]-'a');
    static int ws[N],sa[N<<1];
    for(i=1;i<=tot;++i) ws[dep[i]]++;
    for(i=1;i<=n;++i) ws[i]+=ws[i-1];
    for(i=1;i<=tot;++i) sa[ws[dep[i]]--]=i;
    for(i=tot;i;--i)
    {
        ans-=(ll)dep[pre[sa[i]]]*siz[pre[sa[i]]]*siz[sa[i]];
        siz[pre[sa[i]]]+=siz[sa[i]];
    }
    ans*=2;
    ans+=(ll)(n+1)*n/2*(n-1);
    printf("%lld",ans);
    return 0;
}