记录编号	577626	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3783.[CSP 2022S]星战	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	2.561 s
提交时间	2022-11-15 12:09:42	内存使用	10.40 MiB

#include "bits/stdc++.h"

using i64 = long long;

const int N = 5e5 + 10;
int n, m, q;
i64 a[N], now[N], beg[N];

int main() {
    freopen("csp2022_galaxy.in", "r", stdin); 
    freopen("csp2022_galaxy.out", "w", stdout);

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::mt19937_64 rng(time(0));

    std::cin >> n >> m;

    i64 hash = 0, nowHash = 0;

    for (int i = 1; i <= n; ++ i) {
        a[i] = rng();
        hash += a[i];
    }

    for (int i = 1; i <= m; ++ i) {
        i64 u, v;
        std::cin >> u >> v;

        now[v] += a[u], beg[v] = now[v];
        nowHash += a[u];
    }

    std::cin >> q;

    while (q --) {
        i64 op, u, v; std::cin >> op;

        if (op == 1) {
            std::cin >> u >> v;
            now[v] -= a[u];
            nowHash -= a[u];
        } else if (op == 2) {
            std::cin >> v;
            nowHash -= now[v];
            now[v] = 0;
        } else if (op == 3) {
            std::cin >> u >> v;
            now[v] += a[u];
            nowHash += a[u];
        } else if (op == 4) {
            std::cin >> v;
            nowHash += beg[v] - now[v];
            now[v] = beg[v];
        }
        if (nowHash == hash) {
            std::cout << "YES" << '\n';
        } else {
            std::cout << "NO" << '\n';
        }
    }
    return 0;
}