求两数组归并后的数组最小字典序排列。
嘛，可能本人在贪心这块还是太弱了（或者说什么都弱），如果不知道是字符串题估计也想不起来用sa。
显然看得出归并时字典序小的那个数组先往里面加，这就是要比较两数组后缀的rank，方法就把两串相拼做后缀排序后比较。
这里附下贪心正确性证明，反正我不太会，只是感性认识一下。
Upd:突然想起来这题其实可以hash+二分比较，码量稍小，不想写了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>inline char MIN(T&A,T B){return A<B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A>B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return f?x=-x:x;
}
const int N=+;
int A[N<<],a[N],b[N],l,m,n; int rk[N<<],sa[N<<],cnt[N<<],y[N<<],t=,p;
inline void suffix_sort(){
for(register int i=;i<=l;++i)++cnt[rk[i]=A[i]];
for(register int i=;i<=t;++i)cnt[i]+=cnt[i-];
for(register int i=l;i;--i)sa[cnt[A[i]]--]=i;
for(register int k=;k<l;k<<=,p=){
for(register int i=l-k+;i<=l;++i)y[++p]=i;
for(register int i=;i<=l;++i)if(sa[i]>k)y[++p]=sa[i]-k;
for(register int i=;i<=t;++i)cnt[i]=;
for(register int i=;i<=l;++i)++cnt[rk[y[i]]];
for(register int i=;i<=t;++i)cnt[i]+=cnt[i-];
for(register int i=l;i;--i)sa[cnt[rk[y[i]]]--]=y[i];
swap(rk,y);rk[sa[]]=p=;
for(register int i=;i<=l;++i)rk[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i-]+k]==y[sa[i]+k]?p:++p;
if(p==l)break;t=p;
}//for(register int i=1;i<=l;++i)printf("%d %d\n",i,rk[i]);
}
//
int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);
read(n);for(register int i=;i<=n;++i)A[i]=read(a[i]);A[n+]=;
read(m);for(register int i=;i<=m;++i)A[n+i+]=read(b[i]);A[n+m+]=;
l=n+m+;suffix_sort();int i=,j=;
while(i<=n||j<=m){
if(rk[i]<rk[n+j+])printf("%d ",a[i++]);
else printf("%d ",b[j++]);
}puts("");
return ;
}