题解 P3975 【[TJOI2015]弦论】

xtx1092515503 · 2020-07-28 15:33:22 · 题解

Portal

大家好，这里介绍一种理论复杂度可以优化到O(n)的全新后缀数组解法。

我们默认串下标从0开始。

首先t=0的情况就是经典老题了，不同子串个数。直接遍历ht数组，则每个串会增加n-sa_i-ht_i个新串，并且这就是按照字典序加入的。比较naive，这里就不多说了。显然，它是O(n)的，假如你用DC3的话。

然后就是t=1的情况了。

显然，我们需要知道每个本质不同的子串各出现了多少次。

我们举一个栗子：

aabbababb

它后缀排序后的结果是这样的：

我们发现，它实际上可以被看做一个树形结构来表示字典序：

update：新知道有种名叫“笛卡尔树”的神奇玩意儿……下面的东西似乎就是它的魔改，大体思路和笛卡尔树是相同的……如果已经会笛卡尔树的神仙直接结合笛卡尔树理解就OK了……

我居然自己yy出了笛卡尔树

那么这棵树（姑且把它叫做“ht树”），有什么性质呢？

1. 每个节点所代表的区间，都有着相同的前缀，且该公共前缀长度一定大于等于父亲节点区间的公共前缀长度。例如，(2,3)节点所代表的公共前缀abb，就要长于它父亲节点，(1,3)所代表的ab。

2. 每条极长公共前缀（即长度如果再增长其对应的区间就会缩短的前缀）都唯一对应着树中的一个区间，每个区间也反过来对应唯一的极长公共前缀。从这一点，我们可以得出一条重要结论，即ht树的节点数最多为2n+1，因为极长公共前缀的数量最多是n，然后还有n个大小为1的区间，同时还有一个为了方便当作根的(0,n-1)区间。O(n)级别的节点数，是保障总复杂度仍为O(n)的前提。同时，这极长公共前缀的出现次数，就是区间大小。（这里如果结合笛卡尔树的思想来看，实际上就是对n个后缀与n+1个间隔建立一棵笛卡尔树，故总数是2n+1）

3. 对这棵树先根遍历，访问到的节点所代表的公共前缀是按照字典序排序的。这很好理解，因为原串的所有后缀本来就已经排序过了。

4. 这棵树的大区间在分裂成小区间时，是在\min ht的地方分裂的。在上面那组栗子中看一看是不是？

于是我们就可以构思出一种方法：

我们设len_{(i,j)}表示区间(i,j)所对应的极长公共前缀的长度。则先根遍历ht树，对于当前节点，如果(j-i+1)\times(len_{i,j}-len_{fa})<k，就令k减去左边那一大坨，并继续遍历；否则，答案就在当前节点，输出即可。

显然，按照我们的思路，\min ht是一定要求出来的。这只能使用ST表来求，则复杂度为O(n\log n)。我们接下来会讲解如何消掉那个\log，这里先贴一下单\log的代码：

void solve(int l,int r,int las){
    if(l>r){
        if(id>n-sa[r]-las)id-=n-sa[r]-las;
        else{for(int j=0;j<id+las;j++)putchar(s[sa[r]+j]);exit(0);}
        return;
    }
    int mp=RMQ(l,r);
    if(id>1ll*(ht[mp]-las)*(r-l+2))id-=1ll*(ht[mp]-las)*(r-l+2);
    else{
        for(int j=0;j<las;j++)putchar(s[sa[r]+j]);
        for(int j=las;id>0;id-=(r-l+2),j++)putchar(s[sa[r]+j]);
        exit(0);
    }
    solve(l,mp-1,ht[mp]),solve(mp+1,r,ht[mp]);
}

注意到这里的实现不太一样，solve(l,r,las)，实际上对应的区间应是(l-1,r)。这么写主要是为了方便直接RMQ。这里las即为len_{fa}，而len_{(l,r)}则为ht[mp]。

带\log的完整代码：

#include<bits/stdc++.h>
using namespace std;
int stk[500100],tp,L[500100],R[500100],id,pt;
namespace Suffix_Array{
    const int N=500100;
    int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
    char s[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
            ht[rk[i]]=k;
        }
    }   
}
using namespace Suffix_Array;
int mn[500100][20],LG[500100];
int MIN(int i,int j){
    return ht[i]<=ht[j]?i:j;
}
int RMQ(int l,int r){
    int k=LG[r-l+1];
    return MIN(mn[l][k],mn[r-(1<<k)+1][k]);
}
void solve(int l,int r,int las){
//  printf("%d %d %d\n",l,r,las);
    if(l>r){
        if(id>n-sa[r]-las)id-=n-sa[r]-las;
        else{for(int j=0;j<id+las;j++)putchar(s[sa[r]+j]);exit(0);}
        return;
    }
    int mp=RMQ(l,r);
    if(id>1ll*(ht[mp]-las)*(r-l+2))id-=1ll*(ht[mp]-las)*(r-l+2);
    else{
        for(int j=0;j<las;j++)putchar(s[sa[r]+j]);
        for(int j=las;id>0;id-=(r-l+2),j++)putchar(s[sa[r]+j]);
        exit(0);
    }
    solve(l,mp-1,ht[mp]),solve(mp+1,r,ht[mp]);
}
int main(){
    scanf("%s",s),n=strlen(s),scanf("%d%d",&pt,&id),m='z';
    SA();
//  for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
//  for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
    if(pt==0){
        for(int i=0;i<n;i++){
            if(n-sa[i]-ht[i]<id)id-=n-sa[i]-ht[i];
            else{for(int j=0;j<id+ht[i];j++)putchar(s[sa[i]+j]);id=0;break;}
        } 
        if(id)puts("-1");
    }else{
        for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
        for(int i=1;i<n;i++)mn[i][0]=i;
        for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
//      for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
//      for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
        solve(1,n-1,0);
        puts("-1");
    }
    return 0;
}

至于不带\log的做法，直接建笛卡尔树即可。

然后就是后缀排序部分了。显然，用DC3算法来排序也能够做到O(n)。

则总复杂度O(n)。

感觉可以出一道n\leq5\times 10^6的毒瘤题？

但是隔壁SAM的复杂度好像很轻松就搞到O(n)了？那我还费心思卡这个O(n)干什么……

那就这样吧，笛卡尔树的代码太懒不想写了