图论 + 哈希。
因为实在是太妙了所以写个题解。
Solution
-
因为每个点的出度都为 \(1\)，所以从任意一点出发永远可以走下去，故每次只需判断每个点度数是否为 \(1\) 即可。
-
然后一三操作显然直接 \(O(1)\) 维护，\(50\ pts\)。
-
考虑二四操作。每次操作显然对点 \(u\) 的出度没有影响，但是对边的起点 \(v\) 的出度有影响。考虑如何把操作转化到对 \(u\) 的修改上来。
-
发现可以维护一个点的入度。如果不考虑反攻时刻的判断，四个操作在入度上的修改都能做到 \(O(1)\)。
-
根据入度 = 出度，反攻时刻的判断可以变为所有节点的入度值等于 \(n\)。但是这样无法保证每个节点的出度都是 \(1\)。
-
考虑优化一下入度的计算，实现 \(O(1)\) 判断所有节点的出度一定都为 \(1\)。结合起来考虑，发现如果使用哈希的思想，给每个节点随机权值 \(w_i\)，定义一个节点的入度为所有边起点的权值和，那么如果 \(\sum r_i=\sum w_i\)，则能保证每个节点都有一条出边指向某个节点。
-
解题重点在于转化与哈希思想。如果想到第一条和哈希，此题基本迎刃而解。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 5e5 + 5;
int n, m, q;
int tot, r[maxn], w[maxn], g[maxn];
mt19937 rng(time(0));
signed main(){
scanf("%lld%lld", &n, &m);
rep(i, 1, n) w[i] = rng(), tot += w[i];
int rec = 0;
while(m--){ int u, v; scanf("%lld%lld", &u, &v);
g[v] = (r[v] += w[u]), rec += w[u];
}
scanf("%lld", &q);
while(q--){
int t; scanf("%lld", &t);
if(t == 1){ int u, v; scanf("%lld%lld", &u, &v);
r[v] -= w[u], rec -= w[u];
} else if(t == 2){ int v; scanf("%lld", &v);
rec -= r[v], r[v] = 0;
} else if(t == 3){ int u, v; scanf("%lld%lld", &u, &v);
r[v] += w[u], rec += w[u];
} else{ int v; scanf("%lld", &v);
rec += g[v] - r[v], r[v] = g[v];
} if(rec == tot) printf("YES\n"); else printf("NO\n");
}
return 0;
}
Thanks for reading.