萌新妹子求卡常

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int B = 3500;

int T, n, m, q, d[MAXN]; bitset<MAXN> f[MAXN];

vector<int> g[MAXN], t, tmp;

int tot, a[MAXN], b[MAXN], p[MAXN]; bool vis[MAXN];

int op[MAXN], x[MAXN], y[MAXN], z[MAXN], dp[MAXN], ans[MAXN];

int main() {
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	for (scanf("%*d%d", &T); T--; ) {
		scanf("%d%d%d", &n, &m, &q);
		for (int i = 1; i <= n; i++) g[i].clear();
		for (int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), g[v].emplace_back(u), d[u]++;
		t.clear();
		for (int i = 1; i <= n; i++) if (!d[i]) t.emplace_back(i);
		for (int i = 0; i < n; i++) for (int v : g[t[i]]) if (!--d[v]) t.emplace_back(v);
		for (int i = 1; i <= n; i++) f[i].reset(), f[i].set(i);
		for (int u : t) for (int v : g[u]) f[v] |= f[u];
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), p[a[i]] = i;
		for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
		for (int i = 1; i <= q; i++) {
			scanf("%d%d%d", &op[i], &x[i], &y[i]);
			if (op[i] == 3) scanf("%d", &z[i]);
		}
		int __cnt = 0;
		for (int i = 1; i <= q; i++) ans[i] = 0;
		for (int lq = 1; lq <= q; lq += B) {
			int rq = min(lq + B - 1, q); tmp.clear();
			for (int i = 1; i <= n; i++) vis[i] = 0;
			for (int i = lq; i <= rq; i++) if (op[i] <= 2) vis[x[i]] = vis[y[i]] = 1;
			for (int i = 1; i <= n; i++) if (vis[i]) tmp.emplace_back(i);
			for (int lv = 1; lv <= n; lv += B) {
				int rv = min(lv + B - 1, n);
				for (int i = 1; i <= n; i++) dp[i] = 0;
				for (int i = lv; i <= rv; i++) if (!vis[p[i]]) dp[p[i]] = b[p[i]];
				for (int u : t) for (int v : g[u]) dp[v] = max(dp[v], dp[u]);
				for (int i = lq; i <= rq; i++) {
					if (op[i] == 3 && y[i] <= lv && z[i] >= rv) ans[i] = max(ans[i], dp[x[i]]);
				}
			}
			for (int i = lq; i <= rq; i++) {
				if (op[i] < 3) continue;
				int lp = (y[i] - 1) / B * B + B, rp = (z[i] - 1) / B * B + 1;
				if (lp > rp) {
					for (int j = y[i]; j <= z[i]; j++) {
						if (f[x[i]].test(p[j]) && !vis[p[j]]) ans[i] = max(ans[i], b[p[j]]);
						__cnt++;
					}
				} else {
					for (int j = y[i]; j <= lp; j++) {
						if (f[x[i]].test(p[j]) && !vis[p[j]]) ans[i] = max(ans[i], b[p[j]]);
						__cnt++;
					}
					for (int j = rp; j <= z[i]; j++) {
						if (f[x[i]].test(p[j]) && !vis[p[j]]) ans[i] = max(ans[i], b[p[j]]);
						__cnt++;
					}
				}
			}
			for (int i = lq; i <= rq; i++) {
				if (op[i] == 1) swap(a[x[i]], a[y[i]]), swap(p[a[x[i]]], p[a[y[i]]]);
				if (op[i] == 2) swap(b[x[i]], b[y[i]]);
				if (op[i] == 3) {
					for (int u : tmp) {
						if (f[x[i]].test(u) && y[i] <= a[u] && a[u] <= z[i]) ans[i] = max(ans[i], b[u]);
					}
				}
			}
			fprintf(stderr, "%d\n", lq);
		}
		for (int i = 1; i <= q; i++) if (op[i] == 3) printf("%d\n", ans[i]);
	}
}