题解

思路

1. 判定条件

设当前可用图中点 $u$ 的出度为 $d_u$。

如果所有 $d_u=1$，那么从任意点不断沿唯一出边前进。由于点数有限，路径最终必然进入一个有向环，因此可以无限穿梭；同时唯一出边也满足连续穿梭条件。

反过来，题意直接要求每个点恰有一条可用出边。因此一次操作后的答案等价于判断

$$d_1=d_2=\cdots=d_n=1.$$

不需要显式维护连通性或有向环。

做法

2. 子任务 1：全量扫描

保存每条边的可用状态。单边操作修改一条边，整点操作枚举所有终点为该点的边。每次操作后重新统计所有点的出度并检查是否全为 $1$。

复杂度为 $O(m+q(n+m))$，空间复杂度为 $O(n+m)$，适用于 $n\le60,m\le120,q\le120$。

3. 子任务 2：维护坏点个数

继续显式保存每条边的状态，同时维护每个点的当前出度 $d_u$，以及

$$bad=\#\{u\mid d_u\ne1\}.$$

修改一条边时，只需在修改前后分别判断对应起点是否为坏点。整点操作枚举该终点的所有入边，逐条修改。操作后 $bad=0$ 当且仅当答案为 YES。

复杂度为 $O(n+m+q+\sum \text{被整点操作枚举的入度})$。在第二子任务的规模下，即使每次整点操作都枚举全部边也能通过。

4. 满分算法：随机指纹

为每个起点 $u$ 独立生成三个 64 位随机权值 $h_1(u),h_2(u),h_3(u)$。以下运算均在无符号 64 位整数中自然溢出，即模 $2^{64}$。

对每一维指纹维护

$$S_j=\sum_{(u,v)\text{ 当前可用}}h_j(u),\qquad T_j=\sum_{u=1}^n h_j(u).$$

因为起点 $u$ 的每条可用出边都贡献一次 $h_j(u)$，所以

$$S_j=\sum_{u=1}^n d_u h_j(u).$$

若所有 $d_u=1$，必有三维 $S_j=T_j$。若出度向量错误，三个等式同时误碰撞的概率可以忽略不计；使用运行时随机种子还能避免输入针对固定权值构造。

为了支持整点操作，再为每个终点 $v$ 维护当前可用入边的三维权值和 $C_j(v)$，以及所有原始入边的权值和 $O_j(v)$：

• 摧毁 $(u,v)$：从 $S_j,C_j(v)$ 中减去 $h_j(u)$；
• 修复 $(u,v)$：向 $S_j,C_j(v)$ 中加上 $h_j(u)$；
• 摧毁终点为 $v$ 的全部边：令 $S_j\leftarrow S_j-C_j(v)$，再令 $C_j(v)=0$；
• 修复终点为 $v$ 的全部边：令 $S_j\leftarrow S_j+O_j(v)-C_j(v)$，再令 $C_j(v)=O_j(v)$。

每次操作只做常数次无符号整数运算。总时间复杂度为 $O(n+m+q)$，空间复杂度为 $O(n)$。

本解法是 Monte Carlo 算法。三组独立 64 位指纹将非零错误出度向量被误判的概率压到工程上可忽略的量级；正式数据还使用独立模数指纹 Oracle 与小规模精确算法交叉核验。

复杂度

• 子任务 1：时间 $O(m+q(n+m))$，空间 $O(n+m)$；
• 子任务 2：时间 $O(n+m+q+\sum \text{整点操作枚举的入度})$，空间 $O(n+m)$；
• 满分算法：时间 $O(n+m+q)$，空间 $O(n)$。

易错点

1. 第 2、4 类操作修改的是终点为指定点的虫洞，而不是从该点出发的虫洞。
2. 第 4 类操作必须恢复该终点的全部原始入边，包括此前被第 1 类操作单独摧毁的边。
3. 只判断当前可用边数是否等于 $n$ 不够；不同起点的出度可能分别为 $0$ 和 $2$。
4. 单边操作的合法性由输入保证，整点操作则允许没有实际效果。
5. 指纹和乘加必须使用无符号 64 位类型，避免有符号溢出未定义行为。