我该在哪里停留？我问我自己。
题目链接
很难想象专门有一道题目考察bitset。
这道题目的 \(O(nq)\) 做法是显然的，预处理就行了。
考虑转化一下限制：令集合 \(S\) 表示可用点的集合，则 \(S = \{ i|u\to i,l\le a_i \le r\}\)。然后取点集中 \(b\) 的最大值即可。
那么可以拆一下限制：第一个限制是好处理的，在 DAG 图上可以使用 bitset 做到 \(O(nm/w)\)。对于第二部分，我们可以使用小巧思。
令集合 \(A_x = \{ i|a_i\ge x\}\)。则限制也就变为了 \(A_l - A_r\)。因此可以考虑分块，把 \(n\) 分成 \(\sqrt n\) 段，维护bitset，修改操作直接更新每一段，查询操作散块直接查，整块使用 xor 处理就行了。
然后再考虑怎么处理 \(b\)，可以维护与 \(a\) 同样的 \(B_x\)，从大到小尝试与 \(x\) 求交，如果有交，可以直接在块里找答案。
这里需要注意需要手写 bitset，不然会因为求交的次数过多直接 TLE。
Code
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
#define ull unsigned long long
const int siz = 1570;
const int N = 1e5 + 10;
const int M = 340;
int n,m,Q;
struct bitst{ull a[siz];void reset(){memset(a,0,sizeof a);}void set(int x){a[(x >> 6)] |= 1ull << (x & 63ll);}void flip(int x){a[x>>6] ^= 1ull << (x & 63ll);}void operator &= (bitst o){for(int i=0;i<siz;i++) a[i] &= o.a[i];}void operator |= (bitst o){for(int i=0;i<siz;i++) a[i] |= o.a[i];}void operator ^= (bitst o){for(int i=0;i<siz;i++) a[i] ^= o.a[i];}int ask(int x){return (a[x >> 6] >> (x & 63))& 1;}
};
bitst A[M],B[M];
bitst to[N];
int a[N],b[N];
int ia[N],ib[N];
vector<int> G[N];
int L[M],R[M];
int len;
void solve(){for(int i=1;i<=n;i++) G[i].clear(),to[i].reset();for(int i=1;i<=len;i++) A[i].reset(),B[i].reset();cin >> n >> m >> Q;int S = sqrt(n);len = (n-1) / S + 1;for(int i=1;i<=len;i++){L[i] = R[i-1];R[i] = i * S;}R[len] = n;for(int i=1;i<=m;i++){int u,v;cin >> u >> v;G[u].push_back(v);}for(int i=1;i<=n;i++){cin >> a[i];ia[a[i]] = i;int block = (a[i] - 1) / S + 1;A[block].set(i);}for(int i=1;i<=n;i++){cin >> b[i];ib[b[i]] = i;int block = (b[i] - 1) / S + 1;B[block].set(i);}for(int i=len;i;i--){A[i] |= A[i+1];B[i] |= B[i+1];}for(int i=n;i>=1;i--){to[i].set(i);for(int v : G[i]) to[i] |= to[v];}while(Q -- ){int op;cin >> op;if(op == 1){int x,y;cin >> x >> y;int l,r;l = (a[x] - 1) / S + 1;r = (a[y] - 1) / S + 1;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(op == 2){int x,y;cin >> x >> y;int l,r;l = (b[x] - 1) / S + 1;r = (b[y] - 1) / S + 1;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;bitst bt;bt.reset();int block_l = (l - 1) / S + 1;int block_r = (r - 1) / S + 1;if(block_l+1 <= block_r){bt = A[block_l+1];bt ^= A[block_r];}for(int i=l;i<=R[block_l];i++) bt.set(ia[i]);for(int i=L[block_r];i<=r;i++) bt.set(ia[i]);bt &= to[x];int pos=0;for(int i=0;i<siz && pos < len;i++){while(bt.a[i] & B[pos+1].a[i]) pos ++ ;}int ans = 0;for(int i=R[pos];i>=L[pos];i--){if(bt.ask(ib[i])){ans = i;break;}}cout << ans << "\n";}}
}
int main()
{
// File("recall");IOS;int c,T;cin >> c >> T;while(T -- ) solve();return 0;
}