11369

Nygglatho · 2025-04-14 02:49:26 · 题解

这个和追忆类似，考虑除以 \omega 的做法。

首先您需要知道 bitset 优化 bfs，这个是 O(\dfrac{n^2}{\omega}) 的，在 m 是 O(n^2) 级别的时候比较有用。

然后是 DAG 的可达性问题，这个可以用 DP 实现，令 f_{i,j} 表示 i 是否能到 j，有 f_{u,j}=f_{v_1,j}\lor f_{v_2,j}\lor f_{v_3,j}\lor\cdots（v 表示存在 u\to v 的边） ，这个根据拓扑序倒序更新 DP 的值，然后可以用 bitset 优化，复杂度是 O(\dfrac{mq}{\omega}) 的，其中 q 是 j 的数量。

把询问离线下来然后按 B 分块，每 B 个操作一起处理，我们令「关键点」集合 S 为这 B 个操作（查询，修改）出现的所有点的集合，「关键边」集合 T 为这 B 个操作中不改变颜色且颜色为黑色的边的集合。显然可以发现 S 是 O(B) 级别的。

然后先以 T 中的边和原图中的所有点建一张图 G，对 G 做一遍 Tarjan 缩点，在缩点后的图 G' 跑 DAG 可达性，我们令 f_{i,j} 表示 G' 中的点 i 在原图对应的 SCC 中的点能否走到 j（j 是 S 中的点），显然 f_{i,j}=1 当且仅当 j 在 i 原图对应的 SCC 中。然后 bitset 优化转移的过程，就可以把 f 求出来了。这里 j 的数量是 O(B) 的，单次复杂度 O(\dfrac{Bm}{\omega})，会做 O(\dfrac{q}{B}) 次，总复杂度 O(\dfrac{qm}\omega)。

进一步地，求出这个之后可以求出来 S 中任意两个点之间只经过 T 中的边的可达性，建一个新的图 G_2，先根据前面把 S 中两个点 u,v，初始时存在 u\to v 的边当且仅当如果只经过「关键边」u 能到达 v。

这样有一个好处就是无论是修改还是查询，都可以只在 G_2 中完成。

• 对于修改操作，在 G_2 中加入或删除该边即可。注意可能会有初始 G_2 中存在这条边的情况需要判一下，也可以把临时在操作中修改的边另外建一个 bitset 单独维护。
• 对于查询，根据 bitset 优化 bfs 即可，注意这里 G_2 的边数是 O(B^2) 级别的，故使用 bitset。

分析一下复杂度，单次查询是 O(\dfrac{B^2}\omega) 的，总复杂度 O(\dfrac{qB^2}\omega)。

加起来就是 O(\dfrac{qm}\omega+\dfrac{qB^2}{\omega})，可以取 B=225。

struct Info {
    int u, v;
} _e[N << 1];

struct Qry {
    int op, x, y;
} _q[N << 1];

bitset <L> w[N], ge[L], gf[L], info, vis;
bitset <N << 1> ans, etag, qtag;

int dfn[N], low[N], ins[N], _dfn, cnt, col[N];

vector <int> e[N], e2[N];
stack <int> s;

void Tarjan (int now) {
    dfn[now] = low[now] = ++ _dfn;
    ins[now] = 1;
    s.push (now);
    for (auto i : e[now]) {
        if (! dfn[i]) {Tarjan (i); low[now] = min (low[now], low[i]);}
        else if (ins[i]) low[now] = min (low[now], low[i]);
    }

    if (dfn[now] == low[now]) {
        ++ cnt;
        for (;;) {
            int _ = s.top (); s.pop ();
            col[_] = cnt;
            ins[_] = 0;
            if (_ == now) break;
        }
    }
}

int mp[N], id[L], _cnt;

map <pair <int, int>, int> Mp;

void Main (int _l) {
    int _r = min (_l + B - 1, q);
    qtag.reset ();
    F (i, 1, n) w[i].reset ();
    _cnt = 0;
    memset (mp, 0, sizeof (mp)); memset (id, 0, sizeof (id));

    F (i, _l, _r) {
        auto [op, x, y] = _q[i];
        if (op == 1) {
            qtag[x] = 1;
            if (! mp[_e[x].u]) {
                ++ _cnt;
                id[_cnt] = _e[x].u, mp[_e[x].u] = _cnt;
            }
            if (! mp[_e[x].v]) {
                ++ _cnt;
                id[_cnt] = _e[x].v, mp[_e[x].v] = _cnt;
            }
        } else {
            if (! mp[x]) {
                ++ _cnt;
                id[_cnt] = x, mp[x] = _cnt;
            }
            if (! mp[y]) {
                ++ _cnt;
                id[_cnt] = y, mp[y] = _cnt;
            }
        }
    }

    memset (dfn, 0, sizeof (dfn)); memset (col, 0, sizeof (col)); memset (ins, 0, sizeof (ins));

    F (i, 1, n) e[i].clear (), e2[i].clear ();

    F (i, 1, m) 
        if (etag[i] && ! qtag[i]) e[_e[i].u].push_back (_e[i].v);
    _dfn = cnt = 0; while (! s.empty ()) s.pop ();
    F (i, 1, n)
        if (! dfn[i]) Tarjan (i); // 缩点，可以发现缩点后的点编号就是倒着的拓扑序
    F (i, 1, _cnt) w[col[id[i]]][i] = 1;
    F (i, 1, _cnt) ge[i].reset (), gf[i].reset ();
    F (i, 1, m) {
        if (etag[i] && ! qtag[i] && col[_e[i].u] != col[_e[i].v]) e2[col[_e[i].u]].push_back (col[_e[i].v]);
        if (etag[i] && qtag[i]) gf[mp[_e[i].u]][mp[_e[i].v]] = 1;
    }
    F (i, 1, cnt)
        for (auto j : e2[i]) w[i] |= w[j];
    F (i, 1, _cnt) F (j, 1, _cnt)
        ge[i][j] = w[col[id[i]]][j]; // 求出两两可达性
    F (i, _l, _r) {
        auto [op, x, y] = _q[i];
        if (op == 1) {
            etag[x] = ! etag[x];
            if (etag[x]) ++ Mp[{_e[x].u, _e[x].v}]; // 重边
            else -- Mp[{_e[x].u, _e[x].v}];
            if (Mp[{_e[x].u, _e[x].v}]) gf[mp[_e[x].u]][mp[_e[x].v]] = 1;
            else gf[mp[_e[x].u]][mp[_e[x].v]] = 0; // 修改，这里是用两个 bitset，维护两两可达性和在询问区间中加的边
        } else {
            info.reset (); vis.reset ();
            x = mp[x], y = mp[y];
            info[x] = 1;
            while (! info[y]) {
                int pos = (info & ~vis)._Find_first ();
                if (pos == info.size ()) {
                    ans[i] = 0; break;
                }
                vis[pos] = 1;
                info |= (ge[pos] | gf[pos]); // bitset 优化 bfs
            }
        }
    }

}

int main () {
    IOS
    cin >> n >> m >> q;
    F (i, 1, m) cin >> _e[i].u >> _e[i].v;
    F (i, 1, m) Mp[{_e[i].u, _e[i].v}] = 1;
    etag.set (); ans.set ();
    F (i, 1, q) {
        cin >> _q[i].op >> _q[i].x;
        if (_q[i].op == 2) cin >> _q[i].y;
    }
    for (int i = 1; i <= q; i += B) Main (i);

    F (i, 1, q) {
        if (_q[i].op == 2) {
            cout << ((ans[i] == 1) ? ("YES\n") : ("NO\n"));
        }
    }
}