P8819
dbxxx
·
·
题解
欢迎到我的博客中查看本文，谢谢！
修改日志：2023 年 7 月 7 日更改，添加一些说明。
先翻译一下题目：
1. 失活某条边；
2. 失活以某个点为终点的所有边；
3. 激活某条边；
4. 激活以某个点为终点的所有边。
然后问：如果只考虑激活的边，是否满足：
- 所有的点出度均为 $1$；
- 所有的点都满足，从这个点出发，可以走到一个环中。
---
首先我们发现，如果所有点的出度均为 $1$，那么所有点都满足从这个点出发能走到一个环里。这是因为所有点的出度都是 $1$，因此一条路径可以一直走下去，而只要走 $n$ 步就一定会遇到先前走过的一个节点（总共只有 $n$ 个点），此时环就出现了。
因此压根不用判环，只用判断所有点出度是否均为 $1$。
> 事实上，所有点出度均为 $1$ 的有向图称作基环内向森林，它由若干个弱联通块（将所有有向边看成无向边后的联通块）构成，每个弱联通块称作基环内向树。对于基环内向树，它可以被认为是由有向环和长在环上的若干条链构成。这些链单向导通到环上。更多有关定义可以自行阅读 [OI Wiki 的图论相关概念](https://oi-wiki.org/graph/concept/#特殊的图)。
我们观察到，一、三操作可以用 $\mathcal{O}(1)$ 的效率修改一个点的出度（修改目标边的终点出度即可），而二、四操作只能用 $\mathcal{O}(n)$ 的效率（因为终点为 $v$ 的边有很多，对应的起点最多有 $n$ 个，它们的出度都需要被修改）。
不过，前 8 个测试点，是支持我们用最坏时间复杂度 $\mathcal{O}(nq)$ 的暴力维护出度的，所以 40 分已经到手。
然后 9 和 10 两个测试点还是保证没有二、四操作的。单次操作可以做到 $\mathcal{O}(1)$。因此这两个测试点用 $\mathcal{O}(q)$ 的复杂度解决，50 分到手。
这里是我的 [50 分代码](https://www.luogu.com.cn/paste/8j8uc74u)。
---
思考许久后我发现，容易维护的不是出度，而是入度。具体来说：
设原图上点 $u$ 的入度为 $g(u)$，当前点 $u$ 入度为 $r(u)$：
1. 失活 $(u, v)$：$r(v) \gets r(v) - 1$；
2. 失活以 $v$ 为终点的所有边：$r(v) \gets 0$；
3. 激活 $(u, v)$：$r(v) \gets r(v) + 1$；
4. 激活以 $v$ 为终点的所有边：$r(v) \gets g(v)$。
这些都可以 $\mathcal{O}(1)$ 完成。
那么入度和出度有什么关系呢？
一张图里，所有点的入度和等于出度和。我们的目标是所有出度都是 $1$，那么所有出度的和都是 $n$。因此入度的和也必须是 $n$。
于是我们得到所有出度均为 $1$ 的一个必要条件：入度和为 $n$。然而这个条件并不充分，因为入度和为 $n$ 可以推出出度和为 $n$，但不能再进一步推出所有出度均为 $1$。
比如，如果有三个点，点 $1$ 出度为 $2$，点 $2$ 出度为 $1$，点 $3$ 没有出度，我们如果单纯地去计算它的入度和，发现它等于 $n$，就判断现在每个点出度都是 $1$，这明显是错误的。
但是，我们可以利用 **哈希** 使得这个条件的充分性有极大概率是正确的，进一步使得这个条件的充要性极大概率正确，通过本题。
---
我们初始给每个点随机一个权值 $w(u)$。重新定义，一个点 $v$ 对应的 $r(v)$，表示直接连向 $v$ 的所有 $u$ 的 $w(u)$ 之和，即：
$$
r(v) = \sum_{(u, v) \in E}w(u)
$$
而 $g(v)$ 代表初始所有边都被激活时的 $r(v)$ 的值，且之后不改变（静态）。
重新设计：
1. 失活 $(u, v)$：$r(v) \gets r(v) - w(u)$；
2. 失活以 $v$ 为终点的所有边：$r(v) \gets 0$；
3. 激活 $(u, v)$：$r(v) \gets r(v) + w(u)$；
4. 激活以 $v$ 为终点的所有边：$r(v) \gets g(v)$。
这个过程中，所有点的 $r$ 值之和 $\sum r(u)$ 可以在每次操作时 $\mathcal{O}(1)$ 地维护。更进一步地：
- 设 $\{u_1, u_2, \ldots\}$ 是 $v$ 的入点集合，则 $r(v) = w(u_1) + w(u_2) + \ldots$。理由是 $r(v)$ 的定义。
- 如果所有点 $u$ 的出度都是 $1$，那么 $u$ 只会出现在它所连向的 $v$ 的入点集合中。因此，将所有入点集合的权值加起来，即 $\sum r(u)$，我们应该恰好得到 $\sum w(u)$。也即，$\sum r(u) = \sum w(u)$。
因此，$\sum r(u) = \sum w(u)$ 是每个点出度都为 $1$ 的一个必要条件。那么，这个条件充分吗？
一般地，我们设点 $u$ 的出度为 $k(u)$，意味着 $w(u)$ 恰好在最终的 $\sum r(u)$ 中出现 $k(u)$ 次。也即 $\sum r(u) = \sum k(u) \times w(u)$。因此我们可以将判断条件 $\sum r(u) = \sum w(u)$ 改写为：$\sum k(u) \times w(u) = \sum w(u)$。
显然所有 $k(u) = 1$ 是一个解。有其它的解吗？
有，但是这样的一组 $k$ 跟 $w$ 高度相关，除非出题人精心构造数据使得目前的局面形成的 $k$ 存在一个不等于 $1$ 还恰好满足这个方程，否则你可以认为当这个方程成立的时候，目前的 $k$ 都等于 $1$。
又因为你的 $w$ 是随机的，所以数据是没法对着你的代码卡的，除非你的 $w$ 正好随机到一个能把你代码卡掉的数据，这种可能太小了基本可以忽略不计，因为随机的值域已经相当大了。
这就是哈希的原理了：判定时构造一个必要不充分条件，但这个“不充分”实际上有非常大非常大的概率充分，以至于不充分性可以忽略不计，从而达到充要判定的效果。读者应当熟悉的字符串哈希，也是同样的原理。
这种哈希似乎一般称作“和哈希”（sum hash）。
```cpp
/*
* @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(); // 这个函数生成随机数的范围和 unsigned int 范围一致，会爆 int。当然你也可以 % 一下
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;
}
```
如果觉得这篇题解写得好，请不要忘记点赞，谢谢！