生日，感慨万千。
我们废话不多说看题，这道题让我们对于一张图维护四个操作
- 删一条边。
- 删一点的所有入边。
- 加入一条被删除的边。
- 加入原图中一个点的所有入边。
每次都要问你一下这个图是不是所有点的出度都是 1。
动态维护一张图是肯定不可能的，可以肯定地说，所有让你动态维护图的题目都不会让你真的去动态维护。而且这道题只是问你所有点出度是不是 1，只要看这个就行了。
所以我们战术弄一个 5e5 位的 (5e5 + 10) 进制数，这个大进制数第 \(i\) 位代表 \(i\) 点的出度。我们记它为 \(square\)。很容易得到出度全是 \(1\) 的时候的目标值，然后就可以 \(O(1)\) 判断了。
下面我们就可以来维护这四个操作了。对于每个点都弄一个 \((5e5 + 10)\) 进制的 \(01\) 串，记为 \(state_u\)，第 \(i\) 位是 \(1\) 代表 \(i\) 有一条到 \(u\) 的边。
- 删除 \((u, v)\) 就是把 \(state_v\) 的第 \(u\) 位变成 \(0\)，相印修改 \(square\)
- 删除 \(u\) 所有入边就是把 \(state_u\) 全部删掉。
3，4 同理。
这个数很大，我们可以模一个大质数，就像哈希一样。上面说的很抽象，具体看代码吧 awa
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
const __int128 Mod[2] = {1000014514191981037, 1000000007998244353};
const __int128 base = 5e5 + 10;
__int128 cm[MAXN + 10][2];
void prepare() {
cm[0][0] = cm[0][1] = 1;
for(int p = 1; p <= MAXN; p++)
for(int i = 0; i < 2; i++)
cm[p][i] = cm[p - 1][i] * base % Mod[i];
}
int d[MAXN + 10];
__int128 state[MAXN + 10][2], start[MAXN + 10][2], square[2], aim[2];
void write(__int128 x) {
int t[25], top = 0;
while(x) {
t[++top] = int(x % 10);
x /= 10;
}
for(int p = top; p >= 1; p--) cout << t[p];
}
void delete1(int u, int v) {
for(int i = 0; i < 2; i++) {
square[i] = ((square[i] - cm[u][i]) % Mod[i] + Mod[i]) % Mod[i];
state[v][i] = ((state[v][i] - cm[u][i]) % Mod[i] + Mod[i]) % Mod[i];
}
}
void delete2(int u) {
for(int i = 0; i < 2; i++) {
square[i] = ((square[i] - state[u][i]) % Mod[i] + Mod[i]) % Mod[i];
state[u][i] = 0;
}
}
void add1(int u, int v) {
for(int i = 0; i < 2; i++) {
square[i] = ((square[i] + cm[u][i]) % Mod[i] + Mod[i]) % Mod[i];
state[v][i] = (state[v][i] + cm[u][i]) % Mod[i];
}
}
void add2(int u) {
for(int i = 0; i < 2; i++) {
square[i] = ((square[i] + start[u][i] - state[u][i]) % Mod[i] + Mod[i]) % Mod[i];
state[u][i] = start[u][i] % Mod[i];
}
}
bool query() {
for(int i = 0; i < 2; i++)
if(square[i] != aim[i]) return 0;
return 1;
}
void print(int ind) {
cout << ind << ":" << endl;
for(int p = 0; p < 3; p++) {
// cout << state[p][0] << ' ' << state[p][1] << endl;
write(state[p][0]);
cout << ' ';
write(state[p][1]);
cout << endl;
}
write(square[0]);
cout << ' ';
write(square[1]);
cout << endl;
}
void init() {
prepare();
int n, m;
cin >> n >> m;
for(int p = 0; p < n; p++)
for(int i = 0; i < 2; i++)
aim[i] = (aim[i] + cm[p][i]) % Mod[i];
for(int p = 1, x, y; p <= m; p++) {
cin >> x >> y;
x--, y--;
d[x]++;
for(int i = 0; i < 2; i++)
start[y][i] = (start[y][i] + cm[x][i]) % Mod[i];
}
for(int p = 0; p < n; p++) {
for(int i = 0; i < 2; i++) {
square[i] = (square[i] + d[p] * cm[p][i]) % Mod[i];
state[p][i] = start[p][i];
}
}
// print(0);
int q; cin >> q;
while(q--) {
int opt, x, y;
cin >> opt;
if(opt == 1) {
cin >> x >> y;
x--, y--;
delete1(x, y);
}
if(opt == 2) {
cin >> x;
x--;
delete2(x);
}
if(opt == 3) {
cin >> x >> y;
x--, y--;
add1(x, y);
}
if(opt == 4) {
cin >> x;
x--;
add2(x);
}
cout << ((query() == 0) ? ("NO") : ("YES")) << endl;
// print(q);
}
}
int main() {
init();
}
这道题还是蛮有创意的说，毕竟 5e5 位的 5e5 进制数咋说都挺离谱，这告诉我们有的时候一个很神奇的方案也可能是正确的。