考虑分块。每个块维护这个块及以后所有点的 bitset，即 $f_{[l,r]}$ 是所有满足 $a_i\ge l$ 的 $i$ 构成的 bitset。内部则维护块内点的后缀并。
对于修改操作，由于 $a$ 是排列，直接暴力修改即可做到 $O(\sqrt{n})$。查询操作是直接合并整块的 bitset 并插入散块，是 $O(\frac{n}{w}+\sqrt{n})$ 的。
这个部分的时间复杂度是 $O(q(\sqrt{n}+\frac{n}{w}))$。
那么现在，我们就可以求出每个查询的有效点集合了。现在的问题是怎样求其中的 $\max b$。
对于 $b$ 我们类似的分块，$g_{[l,r]}$ 是所有满足 $b_i\ge l$ 的 $i$ 构成的 bitset。查询的求最大的 $x$ 使得 $b_i \ge x$ 的 $i$ 构成的 bitset 与有效点有交。$O(\frac{n\sqrt{n}}{w})$。
注意到我们散块和整块的复杂度极度不平衡，仔细分析一下：
* 对于整块，复杂度 $O(\frac{n^2}{Bw})$。修改复杂度为 $O(\frac{n}{B})$。
* 对于散块，修改和查询都是 $O(B)$。
取 $B=10000$，随便跑啊。
[AC Link.](https://www.luogu.com.cn/record/205805945)
更新：官方数据不是出来了吗，太恐怖了，给我原来的代码干 T 了，加一点小卡常就好了（甚至可以说是一些常识？）
1. 去掉 `#define int long long`。
2. `#define endl '\n'`。
[AC Link.](https://www.luogu.com.cn/record/206222406) 也就 2k 出头，不长的。
update:感谢@[hepp](https://www.luogu.com.cn/user/541313) 指出了原题解的错误。在上面的代码中我使用 `.size()` 来判断这个 `bitset` 里是否有 1，但是事实上 `.size()` 返回的是大小而非 1 的个数。导致复杂度退化。但是这玩意能给过了也是神了。应当改为 `.count()` 或 `.any()`。
[新的提交记录](https://www.luogu.com.cn/record/235043893)。
新的代码：
```cpp
#include<bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=2e5+10;
bitset<N>to[N];
vector<int>e[N];
int n,m,q;
const int B1=400,B2=10000;
bitset<N>f[N/B1+10];
bitset<N>g[N/B2+10];
int fid[N],gid[N];
int a[N],b[N],br[N],ar[N];
void solve()
{
cin >> n >> m >> q;
for ( int i = 1 ; i <= n ; i++ )
e[i].clear(),to[i]=0;
for ( int i = 1 ; i <= n ; i++ )
to[i][i]=1;
while(m--)
{
int u,v;cin >> u >> v;
e[u].push_back(v);
}
for ( int i = 1 ; i <= n ; i++ ){
cin >> a[i];ar[a[i]]=i;
}
for ( int i = 1 ; i <= n ; i++ ){
cin >> b[i];br[b[i]]=i;
}
for ( int i = n ; i >= 1 ; i-- )
for ( auto v:e[i] )to[i]|=to[v];
for ( int i = 1 ; i <= n+1 ; i++ )
fid[i]=(i+B1-1)/B1,
gid[i]=(i+B2-1)/B2;
for ( int i = 1 ; i <= fid[n]+1 ; i++ )f[i]=0;
for ( int i = 1 ; i <= gid[n]+1 ; i++ )g[i]=0;
for ( int i = 1 ; i <= n ; i++ )
f[fid[a[i]]][i]=1,
g[gid[b[i]]][i]=1;
for ( int i = fid[n]-1 ; i >= 1 ; i-- )
f[i]|=f[i+1];
for ( int i = gid[n]-1 ; i >= 1 ; i-- )
g[i]|=g[i+1];
while(q--)
{
int op,x,y,l,r;
cin >> op;
if(op==1)
{
cin >> x >> y;
for ( int i = 1 ; i <= fid[a[x]] ; i++ )f[i][x]=0;
for ( int i = 1 ; i <= fid[a[y]] ; i++ )f[i][x]=1;
for ( int i = 1 ; i <= fid[a[y]] ; i++ )f[i][y]=0;
for ( int i = 1 ; i <= fid[a[x]] ; i++ )f[i][y]=1;
swap(a[x],a[y]);
swap(ar[a[x]],ar[a[y]]);
}else if(op==2){
cin >> x >> y;
for ( int i = 1 ; i <= gid[b[x]] ; i++ )g[i][x]=0;
for ( int i = 1 ; i <= gid[b[y]] ; i++ )g[i][x]=1;
for ( int i = 1 ; i <= gid[b[y]] ; i++ )g[i][y]=0;
for ( int i = 1 ; i <= gid[b[x]] ; i++ )g[i][y]=1;
swap(b[x],b[y]);
swap(br[b[x]],br[b[y]]);
}else{
cin >> x >> l >> r;
bitset<N>toa;toa=0;
toa=f[fid[l]+1];
for ( int i = l ; i <= min(n,fid[l]*B1) ; i++ )
toa[ar[i]]=1;
toa^=f[fid[r+1]+1];
for ( int i = r+1 ; i <= min(n,fid[r+1]*B1) ; i++ )
toa[ar[i]]=1-toa[ar[i]];
toa&=to[x];
int flg=0;
for ( int i = gid[n] ; i >= 1 ; i-- )
{
if((g[i]&toa).any())
{
for ( int j = min(n,i*B2) ; j >= (i-1)*B2+1 ; j-- )
if(toa[br[j]])
{
flg=1;
cout << j << endl;
break;
}
}
if(flg)break;
}
if(!flg)cout << 0 << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int c,T;cin >> c >> T;
while(T--)solve();
return 0;
}
```