【BZOJ4278】[ONTAK2015]Tasowanie 后缀数组

2022-07-22 15:03:46

【BZOJ4278】[ONTAK2015]Tasowanie

Description

给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。

Input

第一行包含一个正整数n(1<=n<=200000)，表示A串的长度。

第二行包含n个正整数，其中第i个数表示A[i](1<=A[i]<=1000)。

第三行包含一个正整数m(1<=m<=200000)，表示B串的长度。

第四行包含m个正整数，其中第i个数表示B[i](1<=B[i]<=1000)。

Output

输出一行，包含n+m个正整数，即字典序最小的T串。

Sample Input

6
1 2 3 1 2 4
7
1 2 2 1 3 4 3

Sample Output

1 1 2 2 1 2 3 1 2 3 4 3 4

题解：后缀数组无脑码，将两个串连成一个，中间用极大值隔开，然后跑后缀数组，每次取两个串开头的比较排名就可以了。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int maxn=400010;

int N,M,n,m,maxx;

int r[maxn],ra[maxn],rb[maxn],sa[maxn],st[maxn],rank[maxn];

void work()

{

    int i,j,p,*x=ra,*y=rb;

    for(i=0;i<n;i++)    st[x[i]=r[i]]++;

    for(i=1;i<m;i++)    st[i]+=st[i-1];

    for(i=n-1;i>=0;i--)    sa[--st[x[i]]]=i;

    for(j=p=1;p<n;j<<=1,m=p)

    {

        for(i=n-j,p=0;i<n;i++)    y[p++]=i;

        for(i=0;i<n;i++)    if(sa[i]>=j)    y[p++]=sa[i]-j;

        for(i=0;i<m;i++)    st[i]=0;

        for(i=0;i<n;i++)    st[x[y[i]]]++;

        for(i=1;i<m;i++)    st[i]+=st[i-1];

        for(i=n-1;i>=0;i--)    sa[--st[x[y[i]]]]=y[i];

        for(swap(x,y),i=p=1,x[sa[0]]=0;i<n;i++)

            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;

    }

    for(i=0;i<n;i++)    rank[sa[i]]=i;

}

int main()

{

    int i;

    scanf("%d",&N);

    for(i=0;i<N;i++)    scanf("%d",&r[i]),m=max(m,r[i]);

    scanf("%d",&M);

    for(i=0;i<M;i++)    scanf("%d",&r[N+i+1]),m=max(m,r[N+i+1]);

    r[N]=m+1,n=N+M+2,m+=2;

    work();

    int a=0,b=N+1;

    for(i=0;i<N+M;i++)

    {

        if(rank[a]>rank[b]&&b<N+M+1)

            printf("%d ",r[b++]);

        else

            printf("%d ",r[a++]);

    }

    printf("\n");

    return 0;

}

码农公寓