思路与算法

有向图每点都能反攻等价于每点出度恰为1。维护精确整数F=Σ(deg(u)-1)²，F=0输出YES。原图无重边，当前边仅删除/恢复。按目的点统计批量修改次数f，取f×入度最大的H≤256个目的点为重目标；各目标有基准开关，单边操作相对开关记录异常。 令base[u]为轻目标当前边数加重目标带符号异常，实际出度=base[u]+开启的重邻目标数。维护G_h=Σ(u有原边到h)(deg(u)-1)，预处理I[v,h]=原图中同时指向v和h的源点数。单边变化δ先扫描该源点重邻居求实际出度，再令F增加2δ(deg-1)+1，并对其所有重邻目标G加δ。 批量重置先撤销目标的有效异常，随后基准若需翻转，令δ=±1。重目标用G直接得到其入边源点的(deg-1)之和；轻目标扫描其入边累加base-1，再用开启重目标的I补足，同时更新这些base。统一更新F+=2δsum+indeg，所有G_h+=δI[v,h]。按原顺序回答。边键排序，单边操作用二分查找，避免哈希最坏情况。

正确性说明

若所有出度为1，从任意点不断沿唯一出边走，有限图中必进入环，满足反攻；反攻要求每点恰有一条可选出边，反向必要性成立。平方项非负，所以精确F=0严格充要，不存在随机碰撞。 单边平方差是2δ(deg-1)+1，G按包含该源点的重邻集合变化。目的点整体翻转时所有受影响源点出度同增δ，平方差相加即2δsum+入度；与其他重集合的交集正好I，因此G更新准确。异常先逐个还原到旧基准后再整体翻转，保证删除/恢复覆盖语义而非简单取反。初始base、G、F直接从原图计算，以上保持式归纳保证每步答案真实。

复杂度

设m边q操作。初始化边排序O(m log m)、重目标排序O(n log n)，交集表O(mH)。单边及异常撤销共O(qH+q log m)，重批量O(qH)。轻批量扫描总成本Σ轻f_v indeg_v≤mq/(4H)：记a_v=√(f_v indeg_v)，Σa≤√(qm)；重目标a不小于最大轻值x，故轻平方和≤x(√(qm)-Hx)。总时间O((m+q)H+mq/H+(m+q)log m+n log n)。H=0单独退化为无有效批量重邻扫描。空间O(nH+m+q)；入度≤65535的交集行用16位，大行32位，满规模实测约308MiB。

易错点

原边永远保留用于恢复。单点删除/恢复遵守当前边状态；异常列表允许失效条目但需检查有效标志，每个有效撤销由此前单点操作计费。F用64位，最大不超过m²+n。原图存在零出度源点时始终不可能成功。样例首部缺漏依据原站配图补全，并透明标注。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Operation {
    int type, u, v, edge;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> U(m), V(m), out(n), indeg(n);
    vector<pair<ll, int>> id(m);
    for (int i = 0; i < m; i++) {
        cin >> U[i] >> V[i];
        --U[i];
        --V[i];
        ++out[U[i]];
        ++indeg[V[i]];
        id[i] = {(ll)U[i] * n + V[i], i};
    }
    sort(id.begin(), id.end());
    int q;
    cin >> q;
    vector<Operation> ops(q);
    vector<int> freq(n);
    for (auto &o : ops) {
        cin >> o.type >> o.u;
        --o.u;
        o.v = o.edge = -1;
        if (o.type == 1 || o.type == 3) {
            cin >> o.v;
            --o.v;
            ll key = (ll)o.u * n + o.v;
            auto found = lower_bound(id.begin(), id.end(), make_pair(key, -1));
            assert(found != id.end() && found->first == key);
            o.edge = found->second;
        } else
            ++freq[o.u];
    }
    vector<pair<ll, int>>().swap(id);
    if (find(out.begin(), out.end(), 0) != out.end()) {
        for (int i = 0; i < q; i++)
            cout << "NO\n";
        return 0;
    }
    vector<int> heavy;
    for (int v = 0; v < n; v++)
        if (freq[v] && indeg[v])
            heavy.push_back(v);
    sort(heavy.begin(), heavy.end(), [&](int a, int b) {
        return (ll)freq[a] * indeg[a] > (ll)freq[b] * indeg[b];
    });
    if (heavy.size() > 256)
        heavy.resize(256);
    int H = heavy.size();
    vector<int> which(n, -1);
    for (int h = 0; h < H; h++)
        which[heavy[h]] = h;
    vector<int> inStart(n + 1), inEdges(m);
    for (int v = 0; v < n; v++)
        inStart[v + 1] = inStart[v] + indeg[v];
    vector<int> at = inStart;
    for (int e = 0; e < m; e++)
        inEdges[at[V[e]]++] = e;
    vector<int> hStart(n + 1);
    for (int e = 0; e < m; e++)
        if (which[V[e]] >= 0)
            ++hStart[U[e] + 1];
    for (int u = 0; u < n; u++)
        hStart[u + 1] += hStart[u];
    vector<int> hAdj(hStart[n]);
    at = hStart;
    for (int e = 0; e < m; e++)
        if (which[V[e]] >= 0)
            hAdj[at[U[e]]++] = which[V[e]];
    vector<int> rowId(n, -1), bigId(n, -1);
    int smallRows = 0, bigRows = 0;
    for (int v = 0; v < n; v++)
        if (indeg[v]) {
            if (indeg[v] <= 65535)
                rowId[v] = smallRows++;
            else
                bigId[v] = bigRows++;
        }
    vector<uint16_t> small((size_t)smallRows * H);
    vector<uint32_t> large((size_t)bigRows * H);
    vector<int> outStart(n + 1), outEdges(m);
    for (int u = 0; u < n; u++)
        outStart[u + 1] = outStart[u] + out[u];
    at = outStart;
    for (int e = 0; e < m; e++)
        outEdges[at[U[e]]++] = e;
    for (int u = 0; u < n; u++)
        for (int z = outStart[u]; z < outStart[u + 1]; z++) {
            int v = V[outEdges[z]];
            if (rowId[v] >= 0) {
                size_t base = (size_t)rowId[v] * H;
                for (int z2 = hStart[u]; z2 < hStart[u + 1]; z2++)
                    ++small[base + hAdj[z2]];
            } else {
                size_t base = (size_t)bigId[v] * H;
                for (int z2 = hStart[u]; z2 < hStart[u + 1]; z2++)
                    ++large[base + hAdj[z2]];
            }
        }
    vector<int>().swap(outEdges);
    vector<int>().swap(outStart);
    vector<int>().swap(at);
    auto intersection = [&](int v, int h) -> int {
        return indeg[v] == 0   ? 0
               : rowId[v] >= 0 ? small[(size_t)rowId[v] * H + h]
                               : large[(size_t)bigId[v] * H + h];
    };
    vector<int> base = out;
    for (int u = 0; u < n; u++)
        base[u] -= hStart[u + 1] - hStart[u];
    vector<char> flag(n, 1), exception(m);
    vector<vector<int>> exceptions(n);
    vector<ll> G(H);
    ll F = 0;
    for (int u = 0; u < n; u++)
        F += (ll)(out[u] - 1) * (out[u] - 1);
    for (int h = 0; h < H; h++)
        for (int z = inStart[heavy[h]]; z < inStart[heavy[h] + 1]; z++)
            G[h] += out[U[inEdges[z]]] - 1;
    auto point = [&](int e, int delta) {
        int u = U[e], degree = base[u];
        for (int z = hStart[u]; z < hStart[u + 1]; z++) {
            int h = hAdj[z];
            degree += flag[heavy[h]];
            G[h] += delta;
        }
        F += 2LL * delta * (degree - 1) + 1;
        base[u] += delta;
    };
    for (auto o : ops) {
        if (o.type == 1 || o.type == 3) {
            int e = o.edge, delta = o.type == 1 ? -1 : 1;
            point(e, delta);
            exception[e] ^= 1;
            if (exception[e])
                exceptions[V[e]].push_back(e);
        } else {
            int v = o.u;
            for (int e : exceptions[v])
                if (exception[e]) {
                    point(e, flag[v] ? 1 : -1);
                    exception[e] = 0;
                }
            exceptions[v].clear();
            int desired = o.type == 4;
            if (flag[v] != desired) {
                int delta = desired - (int)flag[v], h = which[v];
                ll sum = 0;
                if (h >= 0)
                    sum = G[h];
                else {
                    for (int z = inStart[v]; z < inStart[v + 1]; z++) {
                        int u = U[inEdges[z]];
                        sum += base[u] - 1;
                        base[u] += delta;
                    }
                    for (int j = 0; j < H; j++)
                        if (flag[heavy[j]])
                            sum += intersection(v, j);
                }
                F += 2LL * delta * sum + indeg[v];
                for (int j = 0; j < H; j++)
                    G[j] += (ll)delta * intersection(v, j);
                flag[v] = desired;
            }
        }
        assert(F >= 0);
        cout << (F == 0 ? "YES\n" : "NO\n");
    }
}