P11831

首先这是个大哥，大哥除了能 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: 代码。

CPP

#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]);
	}
}

文章操作

相关推荐

评论

P11831