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