P8819 CSP-S 2022 星战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
很棒的一道题，虽然一开始阅读理解确实掉了印象分，但后来做出来发现，瑕不掩瑜。
先翻译一下题目：
\(n\) 个点 \(m\) 条边的有向图，每条边都有激活和失活两种状态，初始时均为激活状态。四种操作：
- 失活某条边；
- 失活以某个点为终点的所有边；
- 激活某条边；
- 激活以某个点为终点的所有边。
然后问：如果只考虑激活的边，是否满足：
- 所有的点出度均为 \(1\)；
- 所有的点都满足，从这个点出发，可以走到一个环中。
首先我们发现，如果所有点的出度均为 \(1\)，那么所有点都满足从这个点出发能走到一个环里。这是因为所有点的出度都是 \(1\)，因此一条路径可以一直走下去，而只要走 \(n\) 步就一定会遇到先前走过的一个节点（总共只有 \(n\) 个点），此时环就出现了。
因此压根不用判环，只用判断所有点出度是否均为 \(1\)。
我们观察到，一、三操作可以用 \(\mathcal{O}(1)\) 的效率修改一个点的出度（修改目标边的终点出度即可），而二、四操作只能用 \(\mathcal{O}(n)\) 的效率（因为终点为 \(v\) 的边有很多，对应的起点最多有 \(n\) 个，它们的出度都需要被修改）。
不过，前 8 个测试点，是支持我们用最坏时间复杂度 \(\mathcal{O}(nq)\) 的暴力维护出度的，所以 40 分已经到手。
然后 9 和 10 两个测试点还是保证没有二、四操作的。单次操作可以做到 \(\mathcal{O}(1)\)。因此这两个测试点用 \(\mathcal{O}(q)\) 的复杂度解决，50 分到手。
这里是我的 50 分代码。
思考许久后我发现，容易维护的不是出度，而是入度。具体来说：
设原图上点 \(u\) 的入度为 \(g(u)\)，当前点 \(u\) 入度为 \(r(u)\)：
- 失活 \((u, v)\)：\(r(v) \gets r(v) - 1\)；
- 失活以 \(v\) 为终点的所有边：\(r(v) \gets 0\)；
- 激活 \((u, v)\)：\(r(v) \gets r(v) + 1\)；
- 激活以 \(v\) 为终点的所有边：\(r(v) \gets g(v)\)。
这些都可以 \(\mathcal{O}(1)\) 完成。
那么入度和出度有什么关系呢？
一张图里，所有点的入度和等于出度和。我们的目标是所有出度都是 \(1\)，那么所有出度的和都是 \(n\)。因此入度的和也必须是 \(n\)。
但显然入度和为 \(n\) 时，出度并不一定都是 \(1\)。这是因为 \(2\) 不仅可以从 \(1 + 1\) 得到，还可以从 \(0 + 2\) 得到。
那么，有什么办法正确地判断 \(1 + 1\) 只能是 \(1 +1\)，不能是 \(0 + 2\) 呢？想到了哈希。
我们初始给每个点随机一个权值 \(w(u)\)。重新定义，一个点 \(v\) 对应的 \(r(v)\)，表示直接连向 \(v\) 的所有 \(u\) 的 \(w(u)\) 之和，即：
\[r(v) = \sum_{(u, v) \in E}w(u) \]而 \(g(v)\) 代表初始所有边都被激活时的 \(r(v)\) 的值，且之后不改变（静态）。
重新设计：
- 失活 \((u, v)\)：\(r(v) \gets r(v) - w(u)\)；
- 失活以 \(v\) 为终点的所有边：\(r(v) \gets 0\)；
- 激活 \((u, v)\)：\(r(v) \gets r(v) + w(u)\)；
- 激活以 \(v\) 为终点的所有边：\(r(v) \gets g(v)\)。
这个过程中，所有点的 \(r\) 值之和 \(\sum r(u)\) 是非常好维护的，而如果这个和恰好等于 \(\sum w(u)\)，我们就有极其大的把握说，每个节点的出度均为 \(1\)。
为什么？
这是因为，\(\sum r(u) = \sum w(u)\) 的时候，我们有极其大的把握，说每个点的 \(w(u)\) 恰好只被 \(\sum r(u)\) 统计过一次。
换句话说，关于 \(w\) 数组的方程 \(k_1w_1 + k_2w_2 + k_3w_3 + \cdots = w_1 + w_2 + w_3 + \cdots\)，在 \(w\) 数组随机生成的情况下，极大概率只有一个解：\(k_1 = k_2 = k_3 = \cdots = 1\)。
而这代表每个点 \(u\)，恰好只包含在一个 \(r(v)\) 的组成部分中，也就是说，只有一个点 \(v\) 满足被 \(u\) 连接了，那不就是 \(u\) 的出度为 \(1\) 吗。
时间复杂度 \(\mathcal{O}(q)\)。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-31 05:16:58
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-31 05:23:44
*/
#include <bits/stdc++.h>
#define int long long
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int maxn = (int)5e5 + 5;
int r[maxn], w[maxn], g[maxn];
signed main() {
int n = read(), m = read();
std :: mt19937 rng(time(0));
for (int u = 1; u <= n; ++u)
w[u] = rng();
int tar = std :: accumulate(w + 1, w + n + 1, 0LL);
// 这是求和函数，注意 0 后面要加 LL （否则会爆）
int now = 0;
while (m--) {
int u = read(), v = read();
r[v] += w[u];
g[v] = r[v];
now += w[u];
}
int q = read();
while (q--) {
int t = read();
if (t == 1) {
int u = read(), v = read();
r[v] -= w[u];
now -= w[u];
} else if (t == 2) {
int v = read();
now -= r[v];
r[v] = 0;
} else if (t == 3) {
int u = read(), v = read();
r[v] += w[u];
now += w[u];
} else if (t == 4) {
int v = read();
now += g[v] - r[v];
r[v] = g[v];
}
puts(now == tar ? "YES" : "NO");
}
return 0;
}
如果觉得这篇题解写得好，请不要忘记点赞，谢谢！
标签：入度,星战,出度,所有,失活,2022,mathcal,gets,CSP From： https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p8819.html