题解：P11831 [省选联考 2025] 追忆

· · 题解

下面我将给出一个 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;
}