思路
首先可以知道答案的下界就是序列 \(a\) 原来的 LIS，现在需要做的就是尽可能地保持答案不增加。
可以肯定的是，将序列 \(b\) 从大到小地插入序列 \(a\) 是不劣的，并且如果在 \(a_i\) 前插入的都是 \(\ge a_i\) 的不会使答案增加，可以感性理解，如果原来的 LIS 没有选择 \(a_i\)，那么选择插入的降序序列则会让答案变劣，如果选择了 \(a_i\)，并且在插入后改为下降序列的某一个数字，那么后面的选择会变少，答案一定不会增加。
所以这道题就很明了了。
对于 \(a_i\)，直接将目前剩下的所有 \(\ge a_i\) 的数字按照降序全部在 \(a_i\) 前插入即可，还需要将没插完的 \(b_i\) 在最后降序输出。
AC code
#include<bits/stdc++.h>
using namespace std;
int T,n,m,a[200005],b[200005],p;
inline bool cmp(int a,int b){return a>b;}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m),p=1;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=m;++i) scanf("%d",&b[i]);
sort(b+1,b+m+1,cmp);
for(int i=1;i<=n;++i)
{
while(p<=m&&b[p]>=a[i]) printf("%d ",b[p++]);
printf("%d ",a[i]);
}
for(int i=p;i<=m;++i) printf("%d ",b[i]);
puts("");
}
return 0;
}