专栏文章

11369

NNygglatho
P11369题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipm3s0i
此快照首次捕获于
2025/12/03 14:14
3 个月前
此快照最后确认于
2025/12/03 14:14
3 个月前
查看原文
这个和追忆类似，考虑除以 ω\omega 的做法。
首先您需要知道 bitset 优化 bfs，这个是 O(n2ω)O(\dfrac{n^2}{\omega}) 的，在 mm 是 O(n2)O(n^2) 级别的时候比较有用。
然后是 DAG 的可达性问题，这个可以用 DP 实现，令 fi,jf_{i,j} 表示 ii 是否能到 jj，有 fu,j=fv1,j∨fv2,j∨fv3,j∨⋯f_{u,j}=f_{v_1,j}\lor f_{v_2,j}\lor f_{v_3,j}\lor\cdots（vv 表示存在 u→vu\to v 的边） ，这个根据拓扑序倒序更新 DP 的值，然后可以用 bitset 优化，复杂度是 O(mqω)O(\dfrac{mq}{\omega}) 的，其中 qq 是 jj 的数量。
把询问离线下来然后按 BB 分块，每 BB 个操作一起处理，我们令「关键点」集合 SS 为这 BB 个操作（查询，修改）出现的所有点的集合，「关键边」集合 TT 为这 BB 个操作中不改变颜色且颜色为黑色的边的集合。显然可以发现 SS 是 O(B)O(B) 级别的。
然后先以 TT 中的边和原图中的所有点建一张图 GG，对 GG 做一遍 Tarjan 缩点，在缩点后的图 G′G' 跑 DAG 可达性，我们令 fi,jf_{i,j} 表示 G′G' 中的点 ii 在原图对应的 SCC 中的点能否走到 jj（jj 是 SS 中的点），显然 fi,j=1f_{i,j}=1 当且仅当 jj 在 ii 原图对应的 SCC 中。然后 bitset 优化转移的过程，就可以把 ff 求出来了。这里 jj 的数量是 O(B)O(B) 的，单次复杂度 O(Bmω)O(\dfrac{Bm}{\omega})，会做 O(qB)O(\dfrac{q}{B}) 次，总复杂度 O(qmω)O(\dfrac{qm}\omega)。
进一步地，求出这个之后可以求出来 SS 中任意两个点之间只经过 TT 中的边的可达性，建一个新的图 G2G_2，先根据前面把 SS 中两个点 u,vu,v，初始时存在 u→vu\to v 的边当且仅当如果只经过「关键边」uu 能到达 vv。
这样有一个好处就是无论是修改还是查询，都可以只在 G2G_2 中完成。
  • 对于修改操作，在 G2G_2 中加入或删除该边即可。注意可能会有初始 G2G_2 中存在这条边的情况需要判一下，也可以把临时在操作中修改的边另外建一个 bitset 单独维护。
  • 对于查询，根据 bitset 优化 bfs 即可，注意这里 G2G_2 的边数是 O(B2)O(B^2) 级别的，故使用 bitset。
分析一下复杂度，单次查询是 O(B2ω)O(\dfrac{B^2}\omega) 的，总复杂度 O(qB2ω)O(\dfrac{qB^2}\omega)。
加起来就是 O(qmω+qB2ω)O(\dfrac{qm}\omega+\dfrac{qB^2}{\omega})，可以取 B=225B=225。
CPP
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"));
        }
    }
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...