bzoj千题计划283：bzoj4516: [Sdoi2016]生成魔咒（后缀数组）

时间：2023-03-09 16:43:52
bzoj千题计划283：bzoj4516: [Sdoi2016]生成魔咒（后缀数组）

http://www.lydsy.com/JudgeOnline/problem.php?id=4516

考虑在后面新加一个字母产生的影响

假设是第i个

如果不考虑重复，那么会增加i个不同的字符串

考虑重复的话，就是找到 最小的j，满足s[j……i] 在之前出现过，那么i的贡献就是j-1

即查找与某个串的最长公共后缀

如果把整个串倒过来，就变成了每次在前面加一个，查找最长公共前缀

这个利用后缀数组的height数组可以解决

有一个很显然的结论是：

若ijk满足  rank(i)<rank(j)<rank(k)   或者 rank(i)>rank(j)>rank(k) ，则LCP(i,j)>=LCP(i,k)

所以每次找到 排名在它前面的 第一个串，找到排名在它后面的第一个串

这个串分别与他们求LCS，取大的那个，就是加入i后的重复的串

求LCS用height数组+RMQ，

找排名在它前/后的第一个串可以用平衡树/set

网上看的题解用的树状数组

第一个树状数组 找前面的第一个串，权值=位置，这样找rk[i] 前面最大的即可

第二个树状数组 找后面的第一个串，权值=n-位置+1，就是倒着的，这样就是找n-rk[i] 前面最大的

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100001

#define lowbit(x) (x&-x)

int n,tot;

int a[N],has[N];

int v[N];

int sa[][N],rk[][N];

int height[N];

int p,q=;

int F[N][];

int c[][N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void mul(int k,int *sa,int *rk,int *SA,int *RK)

{

    for(int i=;i<=n;++i) v[rk[sa[i]]]=i;

    for(int i=n;i;--i) if(sa[i]-k>) SA[v[rk[sa[i]-k]]--]=sa[i]-k;

    for(int i=n-k+;i<=n;++i) SA[v[rk[i]]--]=i;

    for(int i=;i<=n;++i)

    RK[SA[i]]=RK[SA[i-]]+(rk[SA[i-]+k]!=rk[SA[i]+k] || rk[SA[i-]]!=rk[SA[i]]);

}

void presa()

{

    memset(v,,sizeof(v));

    for(int i=;i<=n;++i) v[a[i]]++;

    for(int i=;i<=tot;++i) v[i]+=v[i-];

    for(int i=;i<=n;++i) sa[p][v[a[i]]--]=i;

    for(int i=;i<=n;++i) rk[p][sa[p][i]]=rk[p][sa[p][i-]]+(a[sa[p][i-]]!=a[sa[p][i]]);

    for(int k=;k<n;k<<=,swap(p,q)) mul(k,sa[p],rk[p],sa[q],rk[q]);

}

void get_height()

{

    int k=,j;

    for(int i=;i<=n;++i)

    {

        j=sa[p][rk[p][i]-];

        while(i+k<=n && j+k<=n && a[i+k]==a[j+k]) k++;

        height[rk[p][i]]=k;

        if(k) k--;

    }

}

int change(int w,int r)

{

    for(int i=r;i<=n;i+=lowbit(i)) c[w][i]=max(c[w][i],r);

}

int ask(int w,int r)

{

    int ans=;

    for(int i=r;i;i-=lowbit(i)) ans=max(ans,c[w][i]);

    return ans;

}

int rmq(int l,int r)

{

    int k=log2(r-l+);

    return min(F[l][k],F[r-(<<k)+][k]);

}

void solve()

{

    for(int i=;i<=n;++i) F[i][]=height[i];

    for(int j=,k=;k<n;++j,k<<=)

        for(int i=;i+(k<<)-<=n;++i)

            F[i][j]=min(F[i][j-],F[i+k][j-]);

    int pos;

    int pre,suc,lcs;

    long long ans=;

    for(int i=n;i;--i)

    {

        pos=rk[p][i];

        pre=ask(,pos-); suc=n-ask(,n-pos)+;

        lcs=;

        if(pre>=) lcs=max(lcs,rmq(pre+,pos));

        if(suc<=n) lcs=max(lcs,rmq(pos+,suc));

        ans+=n-i+-lcs;

        cout<<ans<<'\n';

        change(,pos); change(,n-pos+);

    }

}

int main()

{

    read(n);

    for(int i=n;i;--i) read(a[i]),has[i]=a[i];

    sort(has+,has+n+);

    tot=unique(has+,has+n+)-has-;

    for(int i=;i<=n;++i) a[i]=lower_bound(has+,has+tot+,a[i])-has;

    presa();

    get_height();

    solve();

    fclose(stdin); fclose(stdout);

    return ;

}

相关文章