A49999 正经题解

题意分析
我们有一个有向图，n个点，m条有向边（每个点的“虫洞”指的是以该点为终点的边）。
敌人打击有两种：
摧毁某条虫洞——只是让这条边不可用，但边仍然存在。
摧毁某个据点——会同时摧毁所有以该点为终点的边（即该点的入边），但不会影响该点出发的边。
我方修复有两种：
修复某条虫洞
修复某个据点—— 修复该点所有被摧毁的入边。
反攻条件：
反击：从任意据点出发，可以无限次虫洞穿梭（即该点在环中或能到达环）。
连续穿梭：当且仅当只有一个从该点出发的虫洞可用时，才能连续穿梭（即每个点的出度 = 1）。
所有据点都满足上述两个条件时，才能反攻。
思路分析
小时候做这题看到数据范围吓哭了，这意味着我们实现的算法只可能是线性复杂度，因此必须着手考虑优化
当整个图中$n$个节点点出度都为$1$时，如果此时每个点都能到达环，则说明该图中没有非环结构，就能确认每个节点都能实现连续穿梭和反击
直接按照图论问题思考不太可行……
那我把图论问题转换一下再做不就是了，定义$a_i$为$i$号节点的哈希权值，$val_i$为初始状态下，$i$号节点所有入边起点的权值和，$f_i$为当前状态下，$i$号节点所有有效入边起点的权值和，$sum$为$\sum_{i=1}^n a_i$，$cnt$为$\sum_{i=1}^n f_i$。由于使用的是$unsigned\ long\ long$来随机，所以在$5 \times10^5$范围内哈希冲突的概率极小，基本可以忽略。
当图满足反攻条件时，每个点出度为$1$，且每个点都能到达一个环，既然每个点恰好只有一条出边，且所有点都能到达环，说明整张图不存在树链结构，整张图由若干个互不相交的简单有向环组成。这个情况下入边集合等于出边集合，因此所有有效入边权值总和$cnt$正好等于$sum$（所有权值总和）。反之，如果图不满足条件（出度不为1或非环构成），$cnt$就不会等于$sum$。
因此我们推出：当$cnt = sum$时，可以反攻。
对于每个操作，按题目与数组表意修改即可。
AC代码

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int N = 500005;
ull a[N], val[N], f[N], sum, cnt;
int n, m, q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    mt19937_64 rng(time(0));
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        a[i] = rng();
        sum += a[i];
    }
    for(int i=1;i<=m;i++){
        int u, v;
        cin >> u >> v;
        val[v] += a[u], f[v] += a[u];
    }
    
    for(int i=1;i<=n;i++){
        cnt += f[i];
    }
    cin >> q;
    while(q--){
        int op, x, y;
        cin >> op;
        if(op==1){
            cin >> x >> y;
            f[y] -= a[x];
            cnt -= a[x];
        }else if(op==2){
            cin >> x;
            cnt -= f[x];
            f[x] = 0;
        }else if(op==3){
            cin >> x >> y;
            f[y] += a[x];
            cnt += a[x];
        }else if(op==4){
            cin >> x;
            cnt += val[x]-f[x];
            f[x] = val[x];
        }
        if(cnt==sum)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    
    return 0;
}

时间复杂度
$O(n+m+q)$，可以处理$n, m, q<=5 \times 10^5$的较大数据。