P11831

Register_int · 2025-03-02 07:20:10 · 题解

首先这是个大哥，大哥除了能 dp 以外没有性质了，所以直接当成黑盒考虑。当然先 O(\frac{n^2}{\omega}) 求出每个点能到达的集合。

对于静态的问题，我们对 a 的值域按 B_1 分块。对于块内，只保留 a 在这段范围内的点跑 dp，查询就大块查答案散块暴力枚举，复杂度 O(\frac{n^2}{B_1}+q(B_1+\frac n{B_1}))。

对于修改，我们定期重构，每隔 B_2 重构一次，所有被修改动到的点全部领出来不算贡献，最后再边改边算。复杂度是 O(\frac{n^2q}{B_1B_2}+q(B_1+\frac n{B_1}+B_2))。取 B_1=B_2=n^{\frac23} 得到最优复杂度 O(\frac{n^2}{\omega}+n^{5/3})。

upd: 代码。

#include <bits/stdc++.h>

using namespace std;

// d0j1a io

typedef long long ll;

const int MAXN = 1e5 + 10;
const int B = 3500;

int T, n, m, q, d[MAXN]; bitset<MAXN> f[MAXN];

vector<int> g[MAXN], t, tmp;

int tot, a[MAXN], b[MAXN], p[MAXN]; bool vis[MAXN];

int op[MAXN], x[MAXN], y[MAXN], z[MAXN], dp[MAXN], ans[MAXN];

int main() {
    for (io.read(T, T); T--; ) {
        io.read(n, m, q);
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1, u, v; i <= m; i++) io.read(u, v), g[v].emplace_back(u), d[u]++;
        t.clear();
        for (int i = 1; i <= n; i++) if (!d[i]) t.emplace_back(i);
        for (int i = 0; i < n; i++) for (int v : g[t[i]]) if (!--d[v]) t.emplace_back(v);
        for (int i = 1; i <= n; i++) f[i].reset(), f[i].set(i);
        for (int u : t) for (int v : g[u]) f[v] |= f[u];
        for (int i = 1; i <= n; i++) io.read(a[i]), p[a[i]] = i;
        for (int i = 1; i <= n; i++) io.read(b[i]);
        for (int i = 1; i <= q; i++) {
            io.read(op[i], x[i], y[i]);
            if (op[i] == 3) io.read(z[i]);
        }
        for (int i = 1; i <= q; i++) ans[i] = 0;
        for (int lq = 1; lq <= q; lq += B) {
            int rq = min(lq + B - 1, q); tmp.clear();
            for (int i = 1; i <= n; i++) vis[i] = 0;
            for (int i = lq; i <= rq; i++) if (op[i] <= 2) vis[x[i]] = vis[y[i]] = 1;
            for (int i = 1; i <= n; i++) if (vis[i]) tmp.emplace_back(i);
            for (int lv = 1; lv <= n; lv += B) {
                int rv = min(lv + B - 1, n);
                for (int i = 1; i <= n; i++) dp[i] = 0;
                for (int i = lv; i <= rv; i++) if (!vis[p[i]]) dp[p[i]] = b[p[i]];
                for (int u : t) for (int v : g[u]) dp[v] = max(dp[v], dp[u]);
                for (int i = lq; i <= rq; i++) {
                    if (op[i] == 3 && y[i] <= lv && z[i] >= rv) ans[i] = max(ans[i], dp[x[i]]);
                }
            }
            for (int i = lq; i <= rq; i++) {
                if (op[i] < 3) continue;
                int lp = (y[i] - 1) / B * B + B, rp = (z[i] - 1) / B * B + 1;
                if (lp > rp) {
                    for (int j = y[i]; j <= z[i]; j++) {
                        if (f[x[i]][p[j]] && !vis[p[j]]) ans[i] = max(ans[i], b[p[j]]);
                    }
                } else {
                    for (int j = y[i]; j <= lp; j++) {
                        if (f[x[i]][p[j]] && !vis[p[j]]) ans[i] = max(ans[i], b[p[j]]);
                    }
                    for (int j = rp; j <= z[i]; j++) {
                        if (f[x[i]][p[j]] && !vis[p[j]]) ans[i] = max(ans[i], b[p[j]]);
                    }
                }
            }
            for (int i = lq; i <= rq; i++) {
                if (op[i] == 1) swap(a[x[i]], a[y[i]]), swap(p[a[x[i]]], p[a[y[i]]]);
                if (op[i] == 2) swap(b[x[i]], b[y[i]]);
                if (op[i] == 3) {
                    for (int u : tmp) {
                        if (f[x[i]][u] && y[i] <= a[u] && a[u] <= z[i]) ans[i] = max(ans[i], b[u]);
                    }
                }
            }
        }
        for (int i = 1; i <= q; i++) if (op[i] == 3) io.writeln(ans[i]);
    }
}