RT,WA on #3:

expected: '73757143', found: '73757070'

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define fi first 
#define sc second
using namespace std;
const int N=2e6+5,inf=1e9+9;
int T,n,m,id,ans;
int a[N],b[N],rk[N];
int I,W,tr[N];
vector<pair<int,bool> >qs[N];
vector<int>qsn;
int uq(int aid,int bw){
	while(I<aid)W+=(bw<a[I]),W-=(bw>a[I++]);
	while(I>aid)W-=(bw<a[--I]),W+=(bw>a[I]);
	return W;
}
void upd(int i){
	for(; i<=id; i+=lowbit(i))
		++tr[i];
}
int qry(int i){
	int res=0;
	for(; i; i-=lowbit(i))
		res+=tr[i];
	return res;
}
int query(int r1,int l2,int w){
	qs[r1].push_back({w,1});
	qs[l2].push_back({w,0});
	qsn.push_back(w);
	return 0;
}
void calc(int la,int ra,int lb,int rb){
	if(lb>rb)return;
	int mb=lb+((rb-lb)>>1),ma,res=inf;
	W=0,I=ma=la;
	for(int i=la; i<=ra; ++i)
		W+=(b[mb]>a[i]);
	for(int i=la; i<=ra; ++i)
		if(res>uq(i,b[mb]))ma=i,res=W;
	calc(ma,ra,mb+1,rb),calc(la,ma,lb,mb-1);
	ans+=res+query(la-1,ra+1,b[mb]);
}
inline void init(){
	memset(rk,0,sizeof*rk*(id+1));
	memset(tr,0,sizeof*tr*(id+1));
	memset(qs,0,sizeof qs);
	n=m=ans=id=0;qsn.clear();
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;rk[++id]=a[n+1]=a[n+2]=inf;
		for(int i=1; i<=n; ++i)
			cin>>a[i],rk[++id]=a[i];
		for(int i=1; i<=m; ++i)
			cin>>b[i],rk[++id]=b[i];
		sort(rk+1,rk+1+id);
		id=unique(rk+1,rk+1+id)-rk-1;
		for(int i=1; i<=n+2; ++i)
			a[i]=lower_bound(rk+1,rk+1+id,a[i])-rk;
		for(int i=1; i<=m; ++i)
			b[i]=lower_bound(rk+1,rk+1+id,b[i])-rk;
		sort(b+1,b+1+m);
		calc(1,n+1,1,m);
		for(int i=1; i<=n+2; ++i){
			upd(a[i]),ans+=qry(id)-qry(a[i]);
			for(auto it:qs[i]){
				if(it.sc)ans+=qry(id)-qry(it.fi);
				if(!it.sc)ans-=qry(it.fi-1);
			}
		}
		for(auto it:qsn)ans+=qry(it-1);
		cout<<ans<<'\n';
		init();
	}
	return 0;
}