E. Optimal Insertion

考虑是把 $b$ 序列中的元素插入到 $a$ 序列中， $b$ 序列插入的相对位置一定是值小的在前面。

对 ${b_i<b_j,i<j}$ ，当前得到 $a n s$ 对逆序数， ${b_i、b_j}$ 之间值在 ${b_i\sim b_j}$ 之间的元素有 $x$ 个，值大于 $b_{j}$ 的元素有 $y$ 个，值小于 $b_{i}$ 的元素有 $z$ 个，那么交换 $b_{i}$ 和 $b_{j}$ 插入的相对位置后当前的逆序数个数为 $a n s + x + 1$ 个。故得证。

枚举 $b_{i}$ ，对 $a$ 序列，小于 $b_{i}$ 的位置设为0，大于 $b_{i}$ 的位置设为1，（等于 $b_{i}$ 的情况稍后考虑），那么 $b_{i}$ 插在 $a_{j}$ 之前构成的逆序数的对数等于 $[1, j - 1]$ 中1的个数加上 $[j, n]$ 中0的个数( $j = 1$ 的时候等于 $[1, n]$ 中0的个数， $j = n + 1$ 的时候等于 $[1, n]$ 中1的个数)。

考虑 ${b_0=0}$ ，所有的位置都是 $1$ ，那么 $b_{0}$ 插在 $a_{j}$ 之前构成的逆序数的对数等于 $j - 1$ 。

插入 ${b_1>b_0}$ 时，部分位置由 $1$ 变为 $0$ ， $p$ 位置的 $1$ 变为0，导致 $[1, p - 1]$ 逆序对数+1， $[p, n + 1]$ 逆序对数-1。

对于等于 $b_{i}$ 的位置，和 $b_{i}$ 不构成逆序数，但对 ${b_j>b_i}$ 构成逆序数。

先离散化

code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e6+7,mod=998244353 ;
int t[maxn<<2],n,m,lazy[maxn<<2];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline void build(int l,int r,int rt) {
	lazy[rt]=0;
	if(l==r) {
		t[rt]=l-1;
		return;
	}
	int mid=(l+r)/2;
	build(lson);
	build(rson);
	t[rt]=min(t[rt<<1],t[rt<<1|1]);
}//0插在pos之前 
void pushdown(int rt) {
	if(lazy[rt]) {
		t[rt<<1]+=lazy[rt];
		t[rt<<1|1]+=lazy[rt];
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		lazy[rt]=0;
	}
}
inline void update(int x,int y,int val,int l,int r,int rt) {
	if(x>y) return;
	if(x<=l&&r<=y) {
		t[rt]+=val;
		lazy[rt]+=val;
		return;
	}
	pushdown(rt);
	int mid=(l+r)/2;
	if(y<=mid) update(x,y,val,lson);
	else if(x>mid) update(x,y,val,rson);
	else {
		update(x,y,val,lson);
		update(x,y,val,rson);
	}
	t[rt]=min(t[rt<<1],t[rt<<1|1]);
}
int tr[maxn];
inline void add(int x) {
	while(x<=n+m+1) {
		tr[x]+=1;
		x+=(x&-x);
	}
}
inline int qry(int x) {
	int res(0);
	while(x) {
		res+=tr[x];
		x-=(x&-x);
	}
	return res;
}
inline void solve() {
	int cnt(0),pos(1);
	ll res(0);
	cin>>n>>m;
	vector<int>a(n+1),b(m+1),A(n+m+1);
	vector<pair<int,int> >p(n+1);
	map<int,int>mp;
	for(int i=1;i<=n+m+1;++i) tr[i]=0;
	for(int i=1;i<=n;++i) {
		cin>>a[i],A[i]=a[i];
	}
	for(int i=1;i<=m;++i) cin>>b[i],A[i+n]=b[i];
	sort(A.begin()+1,A.end());
	sort(b.begin()+1,b.end());
	int nm=unique(A.begin()+1,A.end())-A.begin();
	for(int i=1;i<=n;++i) a[i]=lower_bound(A.begin()+1,A.begin()+nm,a[i])-A.begin();
	for(int i=1;i<=m;++i) b[i]=lower_bound(A.begin()+1,A.begin()+nm,b[i])-A.begin();
	for(int i=n;i;--i) {
		res+=qry(a[i]-1),add(a[i]);
		p[i].first=a[i],p[i].second=i;
	}
	sort(p.begin()+1,p.end());
	build(1,n+1,1);
	ll ans(0);
	for(int i=1;i<=m;++i) {
		while(pos<=n&&p[pos].first<b[i]) {
			update(1,p[pos].second,1,1,n+1,1);
			update(p[pos].second+1,n+1,-1,1,n+1,1);
			++pos;
		} 
		if(b[i]!=b[i-1]) for(int j=pos;j<=n&&p[j].first==b[i];++j)
			update(p[j].second+1,n+1,-1,1,n+1,1);
		ans+=t[1];
		if(b[i]!=b[i+1]||i==m) while(pos<=n&&p[pos].first==b[i]) {
			update(1,p[pos].second,1,1,n+1,1);
			++pos;
		}
	}
	cout<<ans+res<<'\n';
}
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}