P11831 [省选联考 2025] 追忆

· · 题解

思路：

注意到空间和时间挺大的，考虑直接 O(\frac{n^2}{\omega}) 求出每个点可达的 bitset f_x。

对于询问，我们想要知道 a_i \in [l, r] 的 i 的 bitset。

考虑建一个 B 层的线段树，维护区间 a_i \in [l, r] 的 bitset，注意这里我们不用 pushup，即单点修改时，直接从叶子到根修改一遍，复杂度为 O(B)；查询时，我们会进行至多 B 次 bitset 的合并，以及 O(\frac{n}{2^B}) 的散点暴力。

现在我们已经支持 O(B) 的修改，O(B\frac{n}{\omega} + \frac{n}{2^B}) 的区间查询 bitset。

我们将 a_i \in [l, r] 的 i 的 bitset 与 f_u 进行与运算得 f'，剩下的点就是合法的点，我们要找合法点中 b 的最大值。

同样使用这种 B 层的线段树维护 b_i \in [l, r] 的 i 的 bitset，然后在这个线段树上进行二分，若与 f' 与之后还有 1，这个 b 就是存在的。

也至多进行 B 次 bitset 的合并，最后暴力扫散点判断，二分复杂度为 O(B \frac{n}{\omega} + \frac{n}{2^B})，取 B = 4, 5, 6 时跑的快一些。

总时间复杂度为 O(Q(B\frac{n}{\omega} + \frac{n}{2^B}))。

先放一个赛后写的可能会被卡常的代码。

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e5 + 1, B = 4, M = 17; 
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
struct Node{
    int l, r; 
    int dep;
    int lson, rson;
    bitset<N> s[2];
}X[M];
bitset<N> Ans;
int c, rt, T, n, m, q, u, v, op, x, y, l, r, cnt, ans;
int a[N], b[N], pa[N], pb[N];
bitset<N> f[N];
vector<int> E[N];
inline void add(int u, int v){
    E[u].push_back(v); 
}
inline void build(int &k, int l, int r, int dep){
    if(dep >= B)
      return ;
    k = ++cnt;
    X[k].l = l, X[k].r = r;
    X[k].dep = dep;
    X[k].s[0].reset(), X[k].s[1].reset();
    if(l == r)
      return ;
    int mid = (l + r) >> 1;
    build(X[k].lson, l, mid, dep + 1);
    build(X[k].rson, mid + 1, r, dep + 1);
}
inline void update(int k, int i, int v, bool f, int pre = 0){
    if(X[k].dep >= B)
      return ;
    if((f ? b[v] : a[v]) < X[k].l || (f ? b[v] : a[v]) > X[k].r)
      X[k].s[f][pre] = 0;
    X[k].s[f][v] = 1;
    if(X[k].l == X[k].r)
      return ;
    int mid = (X[k].l + X[k].r) >> 1;
    if(i <= mid)
      update(X[k].lson, i, v, f, pre);
    else
      update(X[k].rson, i, v, f, pre);
}
inline void ask(int k, int l, int r){
    if(X[k].l == l && r == X[k].r){
        Ans |= X[k].s[0];
        return ;
    }
    if(X[k].dep == B - 1){
        for(int i = l; i <= r; ++i)
          Ans[pa[i]] = 1;
        return ;
    }
    int mid = (X[k].l + X[k].r) >> 1;
    if(r <= mid)
      ask(X[k].lson, l, r);
    else if(l > mid)
      ask(X[k].rson, l, r);
    else{
        ask(X[k].lson, l, mid);
        ask(X[k].rson, mid + 1, r);
    }
}
inline int ask(int k){
    if(X[k].dep == B - 1){
        for(int i = X[k].r; i >= X[k].l; --i)
          if(Ans[pb[i]])
            return i;
        return 0;
    }
    if(X[k].l == X[k].r)
      return X[k].l;
    if((Ans & X[X[k].rson].s[1]).count())
      return ask(X[k].rson);
    else
      return ask(X[k].lson);
}
inline void solve(){
    cnt = 0;
    n = read(), m = read(), q = read();
    for(int i = 1; i <= n; ++i){
        E[i].clear();
        f[i].reset();
        f[i][i] = 1;
    }
    while(m--){
        u = read(), v = read();
        add(v, u);
    }
    for(int u = n; u >= 1; --u)
      for(auto v : E[u])
        f[v] |= f[u];
    for(int i = 1; i <= n; ++i)
      a[i] = read();
    for(int i = 1; i <= n; ++i)
      b[i] = read();
    build(rt, 1, n, 0);
    for(int i = 1; i <= n; ++i){
        update(rt, a[i], i, 0);
        update(rt, b[i], i, 1);
        pa[a[i]] = i, pb[b[i]] = i;
    }
    while(q--){
        op = read();
        if(op == 1){
            x = read(), y = read();
            if(x == y)
              continue;
            update(rt, a[x], y, 0, x);
            update(rt, a[y], x, 0, y);
            swap(a[x], a[y]);
            swap(pa[a[x]], pa[a[y]]);
        }
        else if(op == 2){
            x = read(), y = read();
            if(x == y)
              continue;
            update(rt, b[x], y, 1, x);
            update(rt, b[y], x, 1, y);  
            swap(b[x], b[y]);
            swap(pb[b[x]], pb[b[y]]);       
        }
        else{
            Ans.reset(); 
            ans = 0;
            u = read(), l = read(), r = read();
            ask(rt, l, r);
            Ans &= f[u];
            if(Ans.count()){
                write(ask(rt));
                putchar('\n');
            }
            else
              puts("0");
        }
    }
}
bool End;
int main(){
    //open("A.in", "A.out");
    c = read(), T = read();
    while(T--)
      solve();
    cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}