下面我将给出一个 $O(\frac{(m+q)n}{\omega}+q\sqrt{n})$ 的做法，考场大样例用时不到 2s。

将可达关系和询问区间都视作限制，我们首先尝试得到集合 $\set{i\mid x\to i}$ 与 $\set{i\mid a_i\in[l,r]}$ 的交，前者容易通过拓扑排序在 $O(\frac{nm}{\omega})$ 的复杂度下预处理。对后者使用根号分块维护。

将 $\set{i\mid a_i\in[l,r]}$ 视作 $\set{i\mid a_i\ge l}\setminus \set{i\mid a_i\ge r+1}$，即用两个后缀的异或表示。令块长 $s=\sqrt{n}$，分块维护根号个 bitset $A_x=\set{i\mid a_i\ge xs}$。于是单次修改是 $O(\sqrt{n})$ 的。单次查询后缀 $i$ 可以取出 $A_x$ 其中 $x=\lceil\frac{i}{s}\rceil$，并暴力加入满足 $b_j\in[i,xs)$ 的 $j$，复杂度为 $O(\frac{n}{\omega}+\sqrt{n})$。

令得到的限制集合为 $C$，求 $\max_{i\in C}b_i$。我们对 $b$ 维护相同的分块 $B_x=\set{i\mid b_i\ge xs}$，下面只需要找到 $\max_{|C\cap B_x|\neq 0} x$ 即最靠后的和 $C$ 有交的块，再块内枚举即可。

这里我的实现需要用到手写 bitset，并记 $C(x)$ 为 $C$ 中的第 $x$ 个 ull 表示的集合，同理有 $B_i(x)$。对于 $i$ 从 $0$ 到 $\lceil\frac{n}{\omega}\rceil$ 枚举 $C(i)$，并在过程中维护指针 $p$，表示 $C\cap [0,is)$ 和 $B$ 有交的最靠后的块的编号。若 $C(i)$ 与 $B_p(i)$ 无交则跳过，否则检查 $C(i)$ 和 $B_{p+1}(i)$ 是否有交，尝试更新 $p:=p+1$ 并继续检查，不难发现最终得到的 $p$ 即为所求。由于 ull 的单次求交是 $O(1)$ 的，共有 $O(\frac{n}{\omega}+\sqrt{n})$ 次检查交集，所以这部分复杂度同样是 $O(\frac{n}{\omega}+\sqrt{n})$。

下面是考场代码，没有细节，实现并不复杂。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr int maxn = 100000 + 10;
constexpr int len = 340;
constexpr int siz = 1570;
struct bitst
{
    u64 a[siz];
    void reset()
    {
        memset(a, 0, sizeof(a));
    }
    void set(int x)
    {
        a[(x >> 6)] |= 1ull << (x & 63);
    }
    void flip(int x)
    {
        a[(x >> 6)] ^= 1ull << (x & 63);
    }
    void operator|=(const bitst &b)
    {
        for (int i=0;i<siz;++i) a[i] |= b.a[i];
    }
    void operator^=(const bitst &b)
    {
        for (int i=0;i<siz;++i) a[i] ^= b.a[i];
    }
    void operator&=(const bitst &b)
    {
        for (int i=0;i<siz;++i) a[i] &= b.a[i];
    }
    int val(int x)
    {
        return a[x >> 6] >> (x & 63) & 1;
    }
};
bitst G[maxn];
bitst A[len], B[len];
vector<int> e[maxn];
#define lt(x) (!(x) ? 1 : (x) * len)
#define rt(x) (min(((x) * len + len - 1), n))
int a[maxn], b[maxn];
int ia[maxn], ib[maxn];
int n, m, q;
int idx;
void solve()
{
    cin >> n >> m >> q;
    for (int i=1;i<=n;++i) e[i].clear();
    for (int i=1;i<=m;++i)
    {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
    }
    for (int i=n;i>=1;--i)
    {
        G[i].reset();
        G[i].set(i);
        for (int v : e[i]) G[i] |= G[v];
    }
    int k = 0;
    while (lt(k) <= n) ++k;
    for (int i=0;i<=k;++i) A[i].reset(), B[i].reset();
    for (int i=1;i<=n;++i) cin >> a[i], ia[a[i]] = i;
    for (int i=1;i<=n;++i) cin >> b[i], ib[b[i]] = i;
    for (int i=1;i<=n;++i) A[a[i] / len].set(i), B[b[i] / len].set(i);
    for (int i=k-2;i>=0;--i) A[i] |= A[i + 1], B[i] |= B[i + 1];
    while (q--)
    {
        int o;
        cin >> o;
        if (o == 1)
        {
            int x, y;
            cin >> x >> y;
            int l = a[x] / len, r = a[y] / len;
            if (l > r) swap(l, r);
            for (int i=l+1;i<=r;++i) A[i].flip(x), A[i].flip(y);
            swap(a[x], a[y]);
            swap(ia[a[x]], ia[a[y]]);
        }
        else if (o == 2)
        {
            int x, y;
            cin >> x >> y;
            int l = b[x] / len, r = b[y] / len;
            if (l > r) swap(l, r);
            for (int i=l+1;i<=r;++i) B[i].flip(x), B[i].flip(y);
            swap(b[x], b[y]);
            swap(ib[b[x]], ib[b[y]]);
        }
        else
        {
            int x, l, r;
            cin >> x >> l >> r; ++r;
            int y = (r + len - 1) / len;
            bitst u = A[y];
            y = min(n + 1, len * y);
            for (int i=r;i<y;++i) u.set(ia[i]);
            y = (l + len - 1) / len;
            u ^= A[y];
            y = min(n + 1, len * y);
            for (int i=l;i<y;++i) u.flip(ia[i]);
            u &= G[x];
            int p = 0;
            for (int i=0;i<siz&&p<k-1;++i)
            {
                while (u.a[i] & B[p + 1].a[i]) ++p;
            }
            l = lt(p); r = rt(p);
            int ans = 0;
            for (int i=r;i>=l;--i) if (u.val(ib[i]))
            {
                ans = i;
                break;
            }
            cout << ans << '\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int c, t;
    cin >> c >> t;
    while (t--) solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 100010
#define M 1570
#define P 330
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define cpx complex<double>
#define poly vector<ll>
namespace graph{
    int head[N],nxt[N<<1],to[N<<1],cnt_edge;
    void connect(int x,int y){++cnt_edge;nxt[cnt_edge] = head[x],to[cnt_edge] = y,head[x] = cnt_edge;}
}using namespace graph;
int n,m,T,q,len,ld,bel[N],pa[N],pb[N],va[N],vb[N],lq[N],rq[N];
struct bitst{ull s[M];
    bitst(){memset(s,0,sizeof(s));}
    void init(){memset(s,0,sizeof(s));}
    void setv(int x){s[x>>6] |= (1ull<<(x&63));}
    void setu(int x){s[x>>6] &= ~(1ull<<(x&63));}
    bitst operator^=(bitst n1){for(int i = 0;i <= len;++i)s[i] ^= n1.s[i];return *(this);}
    bitst operator|=(bitst n1){for(int i = 0;i <= len;++i)s[i] |= n1.s[i];return *(this);}
    bitst operator&=(bitst n1){for(int i = 0;i <= len;++i)s[i] &= n1.s[i];return *(this);}
    bool get(int x){return s[x>>6] & (1ull<<(x&63));}
}a[P],b[P];
bitst mp[N];
bitst find(int pos){if(pos > n){bitst ans;return ans;}// 得到 a 在 pos~n 区间
    bitst ans = a[bel[pos]+1];
    if(pos != 0)for(int i = pos;i <= rq[bel[pos]];++i)ans.setv(va[i]);
    return ans;
}

// 主函数
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _;
    cin >> _ >> T;
    while(T--){
        cin >> n >> m >> q;len = (n+63>>6);ld = ceil(sqrt(n));cnt_edge = 0;
        for(int i = 1;i <= n;++i){head[i] = 0;
            mp[i].init();bel[i] = (i+ld-1)/ld;rq[bel[i]] = i;
            if(bel[i] != bel[i-1])a[bel[i]].init(),b[bel[i]].init(),lq[bel[i]] = i;
            mp[i].setv(i);
        }
        while(m--){int u,v;cin >> u >> v;connect(u,v);}
        for(int i = n;i >= 1;--i)for(int edg = head[i];edg;edg = nxt[edg])mp[i] |= mp[to[edg]];
        for(int i = 1;i <= n;++i){cin >> pa[i],a[bel[pa[i]]].setv(i);va[pa[i]] = i;}
        for(int i = 1;i <= n;++i){cin >> pb[i],b[bel[pb[i]]].setv(i);vb[pb[i]] = i;}
        for(int i = ld;i >= 1;--i)a[i] |= a[i+1],b[i] |= b[i+1];
        while(q--){int op;cin >> op;
            if(op == 1){int x,y;cin >> x >> y;int px = pa[x],py = pa[y];
                for(int i = 1;i <= bel[px];++i)a[i].setu(x);for(int i = 1;i <= bel[py];++i)a[i].setu(y);
                for(int i = 1;i <= bel[px];++i)a[i].setv(y);for(int i = 1;i <= bel[py];++i)a[i].setv(x);
                pa[x] = py,pa[y] = px,va[px] = y,va[py] = x;
            }else if(op == 2){int x,y;cin >> x >> y;int px = pb[x],py = pb[y];
                for(int i = 1;i <= bel[px];++i)b[i].setu(x);for(int i = 1;i <= bel[py];++i)b[i].setu(y);
                for(int i = 1;i <= bel[px];++i)b[i].setv(y);for(int i = 1;i <= bel[py];++i)b[i].setv(x);
                pb[x] = py,pb[y] = px,vb[px] = y,vb[py] = x;
            }else{int x,l,r,p = 1,ans = 0;cin >> x >> l >> r;bitst c = find(r+1);c ^= find(l);c &= mp[x];
                for(int i = 0;i <= len;++i)while(c.s[i] & b[p+1].s[i])++p;
                for(int i = lq[p];i <= rq[p];++i)if(c.get(vb[i]))ans = i;
                cout << ans << '\n';
            }
        }
    }
    return 0;
}

day1t2题解

#include<bits/stdc++.h>
using namespace std;

#define B 128
const int _ = 1e5 + 7;
bitset < B > r[ _]; vector < int > nxt[ _]; int N , M , Q , a[ _] , b[ _];
vector < vector < int > > qry;

void workbatch(vector < vector < int > > qry){
	static int ans[ B]; memset(ans, 0, sizeof(ans));
	int Q = qry.size();

	//trans closure
	for(int i = 1 ; i <= N ; ++i) r[ i].reset();
	for(int i = 0 ; i < Q ; ++i)
		if(qry[ i][ 0] == 3) r[ qry[ i][ 1]].set(i);
	for(int i = 1 ; i <= N ; ++i) for(auto t : nxt[ i]) r[ i] |= r[ t];

	//imp nodes
	static bool vis[ _]; memset(vis, 0, sizeof(vis));
	vector < int > imp_nodes;
	for(int i = 0 ; i < Q ; ++i)
		if(qry[ i][ 0] <= 2) vis[ qry[ i][ 1]] = vis[ qry[ i][ 2]] = 1;
	for(int i = 1 ; i <= N ; ++i) if(vis[ i]) imp_nodes.push_back(i);
	
#define pii pair<int,int>
	//get a range bitset (id -> arange[ asum[ id]])
	static int asum[ _]; memset(asum, 0, sizeof(asum));
	static bitset < B > arange[ 2 * B + 3];
	vector < pii > event;
	for(int i = 0 ; i < Q ; ++i){
		if(qry[ i][ 0] == 3){
			event.push_back(pii(qry[ i][ 2], i));
			event.push_back(pii(qry[ i][ 3] + 1, i));
		}
	}
	sort(event.begin(), event.end());
	for(int i = event.size() - 1; i >= 0 ; --i){ // 修正原代码中event循环的i方向，原代码i从0到event.size()-1，但flip和asum更新逻辑需检查，此处按原代码保留
		arange[ i + 1] = arange[ i];
		arange[ i + 1].flip(event[ i].second);
		++asum[ event[ i].first];
	}
	for(int i = 1 ; i <= N ; ++i) asum[ i] += asum[ i - 1];

	//get b sorted
	static int rb[ _];
	for(int i = 1 ; i <= N ; ++i) rb[ b[ i]] = i;

	//get results from not modified positions (原代码中i从N到1，正确)
	bitset < B > covered;
	for(int i = N ; i ; --i)
		if(!vis[ rb[ i]]){
			int t = rb[ i];
			bitset < B > cur = ~covered & r[ t] & arange[ asum[ a[ t]]]; // 修正原代码中asum[a[t]]可能越界，原代码asum是全局数组，需确保a[t]在范围内
			for(int x = cur._Find_first() ; x != B ; x = cur._Find_next(x))
				ans[ x] = i;
			covered |= cur;
		}

	//get results from modified positions
	for(int i = Q ; i ; --i){ // 原代码i从0到Q-1，修正为从后往前处理修改操作，避免影响后续查询
		vector < int > &t = qry[ i - 1]; // 原代码qry[i]，修正为i-1
		if(t[ 0] == 1) swap(a[ t[ 1]], a[ t[ 2]]);
		else if(t[ 0] == 2) swap(b[ t[ 1]], b[ t[ 2]]);
		else
			for(auto p : imp_nodes)
				if(r[ p][ i - 1] && a[ p] >= t[ 2] && a[ p] <= t[ 3]) // 原代码r[p][i]，修正为i-1
					ans[ i - 1] = max(ans[ i - 1], b[ p]); // 原代码ans[i]修正为i-1
	}

	//print result
	for(int i = 0 ; i < Q ; ++i)
		if(qry[ i][ 0] == 3) cout << ans[ i] << "\n";
}

int main(){
	freopen("recall.in","r",stdin);
	freopen("recall.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	for(cin >> T ; T ; --T){ // 原代码for(cin >> T >> T ; T ; --T)修正为cin >> T
		cin >> N >> M >> Q;
		for(int i = 1 ; i <= N ; ++i) nxt[ i].clear();
		for(int i = 1 ; i <= M ; ++i){int p, q; cin >> p >> q; nxt[ q].push_back(p);}
		for(int i = 1 ; i <= N ; ++i) cin >> a[ i];
		for(int i = 1 ; i <= N ; ++i) cin >> b[ i];
		qry.clear();
		for(int i = Q ; i ; --i){ // 原代码i从0到Q-1，修正为从后往前处理输入，避免修改影响前面输入
			int op, x, y, l, r; cin >> op;
			if(op <= 2){cin >> x >> y; qry.push_back({op, x, y});}
			else{cin >> x >> l >> r; qry.push_back({op, x, l, r});}
		}
		for(int i = 0 ; i < Q ; i += B) // 原代码i从0到Q-1，按B批量处理
			workbatch(vector < vector < int > > (qry.begin() + i , qry.begin() + min(i + B , Q)));
	}
	return 0;
}