首先容易知道 $b$ 序列在 $a$ 中的顺序肯定是从小到大排序的，否则交换 $b$ 中逆序的肯定会更优。

接下来是一个很鬼的结论。

设 $p_i$ 表示考虑仅将 $b_i$ 插入 $a$ 序列中，最优位置是插在 $a_{p_i-1}$ 与 $a_{p_i}$ 之间，注意对于同一个 $i$，$p_i$ 可能有多个。

结论：若 $b_j<b_i$，对于多个 $p_j$ 中的任意一个，均存在 $p_i$ 使得 $p_j\le p_i$。

证明：

先考虑 “最优位置” 怎么求得，对于 $b_j$，我们把 $a$ 中小于 $b_j$ 的数看成 $0$，大于 $b_j$ 的数看成 $1$，那么插入 $b_j$ 位置在 $p_j$ 的贡献即为 $a_1,\cdots ,a_{p_j-1}$ 中 $1$ 的个数加上 $a_{p_j},\cdots ,a_n$ 中 $0$ 的个数。

这里为了证明的直观，我们没有考虑 $a$ 中有和 $b_j$ 相等的数的情况，考虑上这种情况的证明方法也是一样的。

考虑反证法，设 $p_i<p_j$，把序列 $a$ 分成三段：$A=[1,p_i-1]$，$B=[p_i,p_j-1]$，$C=[p_j,n]$。

注意到从 $b_j$ 变为 $b_i$ 后，$a$ 序列中只有会 $1$ 变成 $0$。

设 $A_0,A_1$ 表示 $A$ 中原来 $0,1$ 的个数，$A_0^{\prime },A_1^{\prime }$ 表示从 $b_j$ 变为 $b_i$ 后 $A$ 中 $0,1$ 的个数。$B,C$ 同理定义。

那么 $p_j$ 的贡献为：$A_1+B_1+C_0$。

由于 $p_j$ 是 $b_j$ 的最优位置，所以可知把 $p_j$ 变成 $p_i$ 所在位置不会更优，于是：$(A_1+B_1+C_0)-(A_1+B_0+C_0)\le 0$，即 $B_1-B_0\le 0$。

$p_i$ 的贡献为：$A_1^{\prime }+B_0^{\prime }+C_0^{\prime }$。

若把 $p_i$ 调整到 $p_j$ 所在位置，贡献为：$A_1^{\prime }+B_1^{\prime }+C_0^{\prime }$，与调整前的贡献相减得到 $(A_1^{\prime }+B_1^{\prime }+C_0^{\prime })-(A_1^{\prime }+B_0^{\prime }+C_0^{\prime })=B_1^{\prime }-B_0^{\prime }$，而 $B_1^{\prime }-B_0^{\prime }\le B_1-B_0\le 0$，所以把 $p_i$ 调整到 $p_j$ 所在位置肯定不劣，所以肯定存在 $p_i\ge p_j$。

那么我们可以对于每一个 $b_i$ 直接把它插到 $p_i$ 中去，根据这个结论，这样的插法肯定也是满足按 $b_i$ 从小到大排序的。

更加严谨地说，按这种插法首先保证了 $b$ 和 $a$ 之间的逆序对最少，而根据结论可知此时 $b$ 和 $b$ 之间的逆序对为 $0$，也取到了下界，而 $a$ 和 $a$ 之间的逆序对是本来就固定了的。

现在的问题相当于如何快速求每个 $b_i$ 的最优位置和它的逆序对贡献。

使用线段树维护 $[1,i-1]$ 中 $1$ 的个数 + $[i,n]$ 中 $0$ 的个数的最小值即可。

#include<bits/stdc++.h>#define N 1000010
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)using namespace std;inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^'0');ch=getchar();}return x*f;
}int T,n,m,nn,a[N],b[N],bb[N<<1];namespace AA
{int c[N<<1],lowbit[N<<1];void init(){const int t=2000000;for(int i=1;i<=t;i++) lowbit[i]=(i&-i);}void add(int x,int y){for(;x<=nn;x+=lowbit[x]) c[x]+=y;}int query(int x){int ans=0;for(;x;x-=lowbit[x]) ans+=c[x];return ans;}ll work(){for(int i=1;i<=nn;i++) c[i]=0;ll ans=0;for(int i=n;i>=1;i--){ans+=query(a[i]-1);add(a[i],1);}return ans;}
}namespace BA
{int minn[N<<2],lazy[N<<2];void downn(int k,int v){minn[k]+=v,lazy[k]+=v;}void down(int k){if(lazy[k]){downn(k<<1,lazy[k]);downn(k<<1|1,lazy[k]);lazy[k]=0;}}void up(int k){minn[k]=min(minn[k<<1],minn[k<<1|1]);}void build(int k,int l,int r){lazy[k]=0;if(l==r){minn[k]=l-1;return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);up(k);}void update(int k,int l,int r,int ql,int qr,int v){if(ql<=l&&r<=qr){downn(k,v);return;}down(k);int mid=(l+r)>>1;if(ql<=mid) update(k<<1,l,mid,ql,qr,v);if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,v);up(k);}pii p[N];ll work(){for(int i=1;i<=n;i++)p[i]=mk(a[i],i);sort(p+1,p+n+1);sort(b+1,b+m+1);build(1,1,n+1);ll ans=0;int tmp1=1,tmp2=1;for(int i=1;i<=m;i++){while(tmp2<=n&&p[tmp2].fi<=b[i]){update(1,1,n+1,p[tmp2].se+1,n+1,-1);tmp2++;}while(tmp1<=n&&p[tmp1].fi<b[i]){update(1,1,n+1,1,p[tmp1].se,1);tmp1++;}ans+=minn[1];}return ans;}
}int main()
{AA::init();T=read();while(T--){n=read(),m=read();for(int i=1;i<=n;i++) bb[i]=a[i]=read();for(int i=1;i<=m;i++) bb[n+i]=b[i]=read();sort(bb+1,bb+n+m+1);nn=unique(bb+1,bb+n+m+1)-bb-1;for(int i=1;i<=n;i++) a[i]=lower_bound(bb+1,bb+nn+1,a[i])-bb;for(int i=1;i<=m;i++) b[i]=lower_bound(bb+1,bb+nn+1,b[i])-bb;printf("%lld\n",AA::work()+BA::work());}return 0;
}