思路是将 $b$ 排序后插入的位置有单调性，于是直接上决策单调性分治，主席树计算代价

WA on Test #4 /kk

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e5+5,INF=1e9+1;
int n,m,a[N],b[N],f[N],g[N];
#define mid ((l+r)>>1)
int idx,pre[N],suf[N],L[N<<5],R[N<<5],Max[N<<5];
void insert(int p,int &q,int x,int v,int l=0,int r=INF){
	q=++idx,L[q]=L[p],R[q]=R[p],Max[q]=Max[p];
	Max[q]=max(Max[q],v);
	if(l==r)return;
	if(x<=mid)insert(L[p],L[q],x,v,l,mid);
	else insert(R[p],R[q],x,v,mid+1,r);
}
int query(int p,int x,int y,int l=0,int r=INF){
	if(!p)return 0;
	if(x<=l&&r<=y)return Max[p];
	int res=0;
	if(x<=mid)res=max(res,query(L[p],x,y,l,mid));
	if(mid<y)res=max(res,query(R[p],x,y,mid+1,r));
	return res;
}
#undef mid
int op[N];
void solve(int l,int r,int opl,int opr){
	if(l>r)return;
	int mid=(l+r)>>1,pos=-1,cost=INF;
	for(int i=opl;i<=opr;i++){
		int tmp=query(pre[i],0,b[mid]-1)+query(suf[i+1],b[mid]+1,INF)+1;
		if(cost>tmp)
			pos=i,cost=tmp;
	}
	op[mid]=pos;
	solve(l,mid-1,opl,pos);
	solve(mid+1,r,pos,opr);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _Test;cin>>_Test;
	while(_Test--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=m;i++)cin>>b[i];
		sort(b+1,b+m+1,greater<int>());
		idx=0;
		pre[0]=0;
		for(int i=1;i<=n;i++){
			f[i]=query(pre[i-1],0,a[i]-1)+1;
			insert(pre[i-1],pre[i],a[i],f[i]);
		}
		suf[n+1]=0;
		for(int i=n;i>=1;i--){
			g[i]=query(suf[i+1],a[i]+1,INF)+1;
			insert(suf[i+1],suf[i],a[i],g[i]);
		}
		solve(1,m,0,n);
		for(int i=1,j=1;i<=n+1;i++){
			while(j<=m&&op[j]<i)
				cout<<b[j++]<<' ';
			if(i<=n)cout<<a[i]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}