先立flag：这题O(n)的贪心能写！
感觉细节太多（或者我想的太乱..
然后另谋出路发现求出sa来就是sb题一道
二路归并那个后缀rank小先放哪个！
这题终于让我直观体验到了两个串和在一起中间不加分隔符的后果：样例都过不了..一刻赛艇 ..
然后为什么我的sa跑的这么慢..迷之速度，坐稳了最后一页（不过发现似乎po姐跑的比我还慢2333333
ps：实测输出优化大约能快100ms（对于跑了10s的我完全没什么卵用
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
#define N 111111
using namespace std;
int sc()
{
int i=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(f=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
return i;
}
int sa[400004],rank[400004],t1[400004],t2[400004],cc[400004];
int a[400004];
int n,m,len;
bool cmp(int *y,int a,int b,int k)
{
int a1=y[a],b1=y[b];
int a2=a+k>=len?-1:y[a+k];
int b2=b+k>=len?-1:y[b+k];
return a1==b1&&a2==b2;
}
void make_sa()
{
int *x=t1,*y=t2,m=1010;
for(int i=0;i<len;i++)++cc[x[i]=a[i]];
for(int i=1;i<m;i++)cc[i]+=cc[i-1];
for(int i=len-1;~i;i--)sa[--cc[x[i]]]=i;
for(int k=1;k<len;k<<=1)
{
int p=0;
for(int i=len-k;i<len;i++)y[p++]=i;
for(int i=0;i<len;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(int i=0;i<m;i++)cc[i]=0;
for(int i=0;i<len;i++)++cc[x[y[i]]];
for(int i=1;i<m;i++)cc[i]+=cc[i-1];
for(int i=len-1;~i;i--)sa[--cc[x[y[i]]]]=y[i];
swap(x,y);x[sa[0]]=0;m=1;
for(int i=1;i<len;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?m-1:m++;
}
for(int i=0;i<len;i++)
rank[sa[i]]=i;
}
void print(int x)
{
printf("%d ",x);
}
void pprint(int x)
{
if(!x)putchar('0');
else
{
char s[22]; int n=0;
while(x)s[++n]=x%10+'0',x/=10;
while(n)putchar(s[n--]);
}
putchar(' ');
}
int main()
{
n=sc();for(int i=0;i<n;i++)a[i]=sc(); a[n]=1001;
m=sc();for(int i=1;i<=m;i++)a[i+n]=sc();
len=m+n+1;
make_sa();
int la=0,lb=1;
while(la<n||lb<=m)
{
if(la==n)
for(;lb<=m;lb++)print(a[n+lb]);
else if(lb>m)
for(;la<n;la++)print(a[la]);
else
{
if(rank[la]<rank[lb+n])
print(a[la++]);
else
print(a[(lb++)+n]);
}
}
return 0;
}