[文章目录]
Description
给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。
这不是裸后缀数组吗？直接求一下rank数组，然后判断，将rank小的优先归并
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[201000],m,b[201000];
int r[401000],len,mx,ra[401000],rb[401000],sa[401000],st[401000],ran[401000];
int ans[401000];
void initial_hz()
{
int *x=ra,*y=rb,i,j,k;
for(i=0;i!=len;++i) st[x[i]=r[i]]++;
for(i=1;i!=mx;++i) st[i]+=st[i-1];
for(i=len-1;~i;--i) sa[--st[x[i]]]=i;
for(j=k=1;k<len;j<<=1,mx=k)
{
for(k=0,i=len-j;i<len;++i) y[k++]=i;
for(i=0;i!=len;++i) if(sa[i]>=j) y[k++]=sa[i]-j;
memset(st,0,sizeof(int)*mx);
for(i=0;i!=len;++i) st[x[y[i]]]++;
for(i=1;i!=mx;++i) st[i]+=st[i-1];
for(i=len-1;i>=0;--i) sa[--st[x[y[i]]]]=y[i];
for(swap(x,y),i=k=1,x[sa[0]]=0;i!=len;++i)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?k-1:k++;
}
for(i=0;i!=len;++i) ran[sa[i]]=i;
}
int main()
{
scanf("%d",&n);
for(int i=0;i!=n;++i) scanf("%d",a+i),r[i]=a[i],mx=max(mx,a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d",b+i),r[n+i]=b[i],mx=max(mx,b[i]);
mx++; r[n]=mx; len=n+1+m; r[len++]=mx; mx++;
initial_hz();
int L=0,R=1;
for(int i=1;i<=n+m;++i)
{
if(R>m||(L<n&&ran[L]<ran[n+R])) ans[i]=a[L],L++;
else ans[i]=b[R],R++;
}
printf("%d",ans[1]);
for(int i=2;i<=n+m;++i)
printf(" %d",ans[i]);
return 0;
}