考虑暴力做法，如果在某个序列中 $i$ 的排名 $<j$，就连一条有向边 $i\to j$，然后缩点。如果只考虑一个序列的情况，那已经是一条链了，所以缩点后还是一条链。
记录缩点后链上第 $i$ 个点的大小为 $a_i$，那么答案就是 $n^2-\sum\limits_{i=1}^ms_{i-1}a_i$，其中 $s_i=\sum\limits_{j=1}^ia_j$。

不妨先将元素照第一个序列的大小从小到大排序。
可以发现，一个强连通分量内的元素一定是排序后的一个连续段。
证明只需反证法，假设不连续，那中间的元素也会在强连通分量内，所以肯定连续。

那就考虑强连通分量是如何划分的。
假设 $[1,i]$ 是排序后的一个极大强连通分量，可以证明照第二个序列的大小排序后，这些元素的排名也是 $[1,i]$。
根据对称性，一个强连通分量内的元素一定是排序后的一个连续段，不管是按照哪个序列的大小。
其次证明是前缀，证明同样可以反证法，假如在第二个序列中的排名不是 $[1,i]$，那么第一个序列排名 $[i+1,n]$ 的元素中肯定有在第二个序列中的排名为 $1$，与极大联通块矛盾。
对于后续部分，只需砍掉 $[1,i]$ 后采用相同的证明方法即可。

因此，我们只需要把排序后的序列拆成若干份，满足每份在第二个序列中的排名与其相同即可。
可以采用线段树去维护。记 $pos_x$ 表示元素在第一个序列中的排名，那么对于每个元素 $x$，如果 $pos_x\le s_x-1$，则对区间 $[pos_x,s_x-1]$ 加一。
这样，值为 $0$ 的点就是分界点。因为 $[pos_x,s_x-1]$ 因为 $x$ 的原因必然不合法，而且这也是充要条件。

这样我们就需要用线段树维护区间 $0$ 的位置及答案，并且有区间加区间减，这个维护可以仿照扫描线算矩形面积一样，使用标记永久化来处理。
计算答案只需顺便维护一下每条线段最左、右边的 $0$，合并计算贡献即可。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=1e5+7;
int n,m,id[N],pos[N],a[N],b[N];
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
int cnt[N<<2],v1[N<<2],v2[N<<2];
loli ans[N<<2];
void pushup(int u,int l,int r){
	if(cnt[u]){
		ans[u]=v1[u]=v2[u]=0;
	}else{
		if(l==r){
			ans[u]=0;
			v1[u]=v2[u]=l;
			return;
		}
		v1[u]=v1[ls]?v1[ls]:v1[rs];
		v2[u]=v2[rs]?v2[rs]:v2[ls];
		ans[u]=ans[ls]+ans[rs];
		if(v2[ls]&&v1[rs])ans[u]+=1ll*(v1[rs]-v2[ls])*v2[ls];
	}
}
void build(int u,int l,int r){
    cnt[u]=0;
	if(l==r)return pushup(u,l,r);
	build(ls,l,mid);build(rs,mid+1,r);
	pushup(u,l,r);
}
void update(int u,int l,int r,int x,int y,int k){
	if(x>y)return;
	if(x<=l&&r<=y){cnt[u]+=k;return pushup(u,l,r);}
	if(x<=mid)update(ls,l,mid,x,y,k);
	if(y>mid)update(rs,mid+1,r,x,y,k);
	pushup(u,l,r);
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int T;cin>>T;while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		for(int i=1;i<=n;i++)id[i]=i;
		sort(id+1,id+1+n,[](int x,int y){
			return a[x]<a[y];
		});
		for(int i=1;i<=n;i++)
			pos[id[i]]=i;
		build(1,1,n);
		for(int i=1;i<=n;i++)
			update(1,1,n,i,b[id[i]]-1,1);
		for(int op,x,y;m--;){
			cin>>op>>x>>y;
			if(op==1){
				update(1,1,n,pos[x],b[x]-1,-1);
				update(1,1,n,pos[y],b[y]-1,-1);
				swap(a[x],a[y]);
				swap(id[x],id[y]);
				swap(pos[x],pos[y]);
				update(1,1,n,pos[x],b[x]-1,1);
				update(1,1,n,pos[y],b[y]-1,1);
			}else{
				update(1,1,n,pos[x],b[x]-1,-1);
				update(1,1,n,pos[y],b[y]-1,-1);
				swap(b[x],b[y]);
				update(1,1,n,pos[x],b[x]-1,1);
				update(1,1,n,pos[y],b[y]-1,1);
			}
			cout<<1ll*n*n-ans[1]<<'\n';
		}
	}
	return 0;
}