追忆96ptsWA在最后一个点的第13w行

#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
template<int siz>
struct Block_Bitset {
	typedef unsigned long long byte_t;
	static const int BIT = 64;
	static const int SIZ = siz;
	static const int LEN = SIZ / BIT + (SIZ % BIT != 0);          // 实际数组长度
	unsigned long long c[LEN];                            // 改用 LEN 声明数组
	
	inline void clear(int n = SIZ) {
		n = min(n, SIZ);
		int i1 = n >> 6ULL;
		int i2 = n & 63ULL;  
		memset(c, 0, (i1) * sizeof(byte_t));
		c[i1+1]>>=i2;
		c[i1+1]<<=i2;
	}
	
	Block_Bitset() {
		clear(SIZ);
	}
	
	inline bool get(size_t index) {
		int i1 = index >> 6;
		int i2 = index & 63;
		return (c[i1] >> i2) & 1ULL;    
	}
	
	inline void set(size_t index, bool k) {
		int i1 = index >> 6;                         
		int i2 = index & 63; 
		c[i1]=c[i1]&(~(1ULL<<i2))|((byte_t)k<<i2);
	}
	
	inline void set_xor(size_t index) {
		int i1 = index >> 6;                            
		int i2 = index & 63; 
		c[i1] ^= (1ULL << i2);
	}
	
	inline Block_Bitset<SIZ> operator&(const Block_Bitset& other) {
		int len = min(LEN, other.LEN);
		Block_Bitset<SIZ> res;
		for (int i = 0; i < len; ++i) {
			res.c[i] = c[i] & other.c[i];
		}
		return res;
	}
	
	inline Block_Bitset<SIZ> operator|(const Block_Bitset& other) {
		int len = min(LEN, other.LEN);
		Block_Bitset<SIZ> res;
		for (int i = 0; i < len; ++i) {
			res.c[i] = c[i] | other.c[i];
		}
		return res;
	}
	
	inline Block_Bitset<SIZ> operator^(const Block_Bitset& other) {
		int len = min(LEN, other.LEN);
		Block_Bitset<SIZ> res;
		for (int i = 0; i < len; ++i) {
			res.c[i] = c[i] ^ other.c[i];
		}
		return res;
	}
	
	inline Block_Bitset<SIZ> operator&=(const Block_Bitset& other) {
		int len = min(LEN, other.LEN);
		for (int i = 0; i < len; ++i) {
			c[i] &= other.c[i];
		}
		return *this;
	}
	
	inline Block_Bitset<SIZ> operator|=(const Block_Bitset& other) {
		int len = min(LEN, other.LEN);
		for (int i = 0; i < len; ++i) {
			c[i] |= other.c[i];
		}
		return *this;
	}
	
	inline Block_Bitset<SIZ> operator^=(const Block_Bitset& other) {
		int len = min(LEN, other.LEN);
		for (int i = 0; i < len; ++i) {
			c[i] ^= other.c[i];
		}
		return *this;
	}
	
	inline int find_first() {
		for (int i = 0; i < LEN; ++i) {
			if (c[i] != 0) {
				return i * BIT + __builtin_ctzll(c[i]);
			}
		}
		return siz + 1;
	}
	
	inline int find_next(int pos) {
		int i1 = pos >> 6;                         
		int i2 = pos & 63;                              // 块内偏移
		
		// 在当前块内查找 i2+1 及更高位
		if (i2 + 1 < BIT) {                             // 避免移位越界
			unsigned long long higher = c[i1] >> (i2 + 1);
			if (higher) {
				return (i2 + 1 + __builtin_ctzll(higher)) + i1 * BIT;       // 实际位偏移
			}
		}
		
		// 后续块查找
		for (int i = i1 + 1; i < LEN; ++i) {
			if (c[i] != 0) {
				return i * BIT + __builtin_ctzll(c[i]);
			}
		}
		return siz + 1;
	}
};
const int MAXN=1e5+10;
int m,n,q,c,T;
int head[MAXN],tot,to[MAXN<<1],nex[MAXN<<1];
int a[MAXN],b[MAXN],t,ts;
Block_Bitset<100011> g[100001];//可达性集合
Block_Bitset<100011> sa[320];//a值域分块后缀集合
Block_Bitset<100011> sb[320];//a值域分块后缀集合
Block_Bitset<100011> S,tmp;
inline void init(){
	t=sqrt(n);
	ts=n/t;
	ts+=(n%t!=0);
	tot=0;
	for(int i=1;i<=n;++i){
		g[i].clear();
		g[i].set(i,true);
		head[i]=0;
		sa[0].set(i,true);
		sb[0].set(i,true);
		
	}
	for(int i=0;i<=m;++i){
		nex[i]=to[i]=0;
	}
	for(int i=1;i<=ts;++i){
		sa[i].clear();
		sb[i].clear();
	}
}
inline int get_block(int x){
	return (x/t);
}
inline void modify_a(int p,int k1,int k2){//对a后缀值域分块便于查询，O(sqrt(n))
	if(k1>k2){
		swap(k1,k2);
	}
	for(int i=get_block(k1)+1;i<=get_block(k2);++i){
		sa[i].set_xor(p);
	}
}
inline void modify_b(int p,int k1,int k2){//对b后缀值域分块便于查询，O(sqrt(n))
	if(k1>k2){
		swap(k1,k2);
	}
	for(int i=get_block(k1)+1;i<=get_block(k2);++i){
		sb[i].set_xor(p);
	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>c>>T;
	while(T--){
		cin>>n>>m>>q;
		init();
		for(int i=1;i<=m;++i){
			int u,v;
			cin>>u>>v;
			to[++tot]=v;
			nex[tot]=head[u];
			head[u]=tot;
		}
		for(int i=1;i<=n;++i){
			cin>>a[i];
			modify_a(i,0,a[i]);
		}
		for(int i=1;i<=n;++i){
			cin>>b[i];
			modify_b(i,0,b[i]);
		}
		for(int i=n-1;i>=1;--i){//拓扑可达性集合 O(nm/w)
			for(int j=head[i];j;j=nex[j]){
				g[i]|=g[to[j]];
			}
		}
		for(int i=1;i<=q;++i){
			int opt;
			cin>>opt;
			if(opt==1){//O(qsqrt(n))
				int x,y;
				cin>>x>>y;
				modify_a(x,a[x],a[y]);
				modify_a(y,a[y],a[x]);
				swap(a[x],a[y]);
			}
			else if(opt==2){
				int x,y;
				cin>>x>>y;
				modify_b(x,b[x],b[y]);
				modify_b(y,b[y],b[x]);
				swap(b[x],b[y]);
			}
			else{
				int x,l,r;
				cin>>x>>l>>r;
				int bl=get_block(l),br=get_block(r);
				S=sa[bl+1]^sa[br];
				tmp=sa[bl]^sa[bl+1];
				for(int pos=tmp.find_first();pos<=n;pos=tmp.find_next(pos)){//O(qn/w)
					if(a[pos]>=l&&a[pos]<=r){
						S.set(pos,true);
					}
				}
				tmp=sa[br]^sa[br+1];
				for(int pos=tmp.find_first();pos<=n;pos=tmp.find_next(pos)){
					if(a[pos]>=l&&a[pos]<=r){
						S.set(pos,true);
					}
				}
				S&=g[x];
				int p=0,pos=0,lst,ans=0;
				while(pos<sb[0].LEN){
					if(sb[p].c[pos]&S.c[pos]){
						++p;
					}
					else{
						++pos;
					}
				}
				S&=sb[p-1];
				for(pos=S.find_first();pos<=n;pos=S.find_next(pos)){
					ans=max(ans,b[pos]);
				}
				cout<<ans<<endl;
			}
		}
	}
	return 0;
}