自动搬运

查看原文

来自洛谷，原作者为

	yuanruiqi 我该在哪里停留？我问我自己。

搬运于2025-08-24 23:10:35，当前版本为作者最后更新于2025-03-02 19:21:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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