【题解】LOJ-121-「离线可过」动态图连通性

Posted on Edited on In Disqus:

题目

https://loj.ac/problem/121

题意

略

题解

线段树分治

  • 计算出每条边出现的时间区间，拆分到线段树上的若干个结点中。然后在线段树上跑 dfs，回答叶子节点上的询问。
  • 复杂度 \(O(n\log ^2n)\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 5E3 + 100, maxm = 5E5 + 100;

namespace uf {
    int fa[maxn], sz[maxn];
    int undo[maxn], top;
    void init() { memset(fa, -1, sizeof fa); memset(sz, 0, sizeof sz); top = 0; }
    int findset(int x) { while (fa[x] != -1) x = fa[x]; return x; }
    bool join(int x, int y) {
        x = findset(x); y = findset(y);
        if (x == y) return false;
        if (sz[x] > sz[y]) swap(x, y);
        undo[top++] = x;
        fa[x] = y;
        sz[y] += sz[x] + 1;
        return true;
    }
    inline int checkpoint() { return top; }
    void rewind(int t) {
        while (top > t) {
            int x = undo[--top];
            sz[fa[x]] -= sz[x] + 1;
            fa[x] = -1;
        }
    }
}

struct Query {
    int tp, u, v, l, r;
} q[maxm << 1];
vector<Query*> qs;
vector<bool> ans;

vector<Query*> node[maxm << 2];
#define mid ((l + r) >> 1)
#define lson o * 2, l, mid
#define rson o * 2 + 1, mid + 1, r
void ins(Query*& q, int o, int l, int r) {
    if (q->l > r || l > q->r) return;
    if (q->l <= l && r <= q->r) { node[o].push_back(q); return; }
    ins(q, lson); ins(q, rson);
}
void go(int o, int l, int r) {
    if (l > r) return;
    int checkpoint = uf::checkpoint();
    for (auto& q: node[o]) if (q->tp != 2) uf::join(q->u, q->v);
    for (auto& q: node[o])
        if (q->tp == 2) ans.push_back(uf::findset(q->u) == uf::findset(q->v));
    if (l < r) { go(lson); go(rson); }
    uf::rewind(checkpoint);
}

int main() {
    uf::init();
    int n, m;
    cin >> n >> m;
    int clk = 1;
    map<pair<int, int>, int> mp;
    FOR (i, 0, m) {
        scanf("%d%d%d", &q[i].tp, &q[i].u, &q[i].v);
        if (q[i].tp == 2) { q[i].l = q[i].r = clk; qs.push_back(&q[i]); continue; }
        ++clk;
        if (q[i].u > q[i].v) swap(q[i].u, q[i].v);
        if (q[i].tp == 0) mp.insert({{q[i].u, q[i].v}, clk});
        else {
            auto it = mp.find({q[i].u, q[i].v});
            assert(it != mp.end());
            q[i].l = it->second; q[i].r = clk - 1;
            mp.erase(it);
            qs.push_back(&q[i]);
        }
    }
    vector<Query> ex;
    for (auto& x: mp) {
        q[m] = {1, x.first.first, x.first.second, x.second, clk};
        qs.push_back(&q[m++]);
    }

    for (auto& q: qs) ins(q, 1, 1, clk);
    go(1, 1, clk);
    for (auto x: ans) puts(x ? "Y" : "N");
}

时间最大生成树

  • 对所有操作按照询问的时间点和边存在的起始时间排序，维护时间最大生成树。
  • 加入一条边时：
    • 如果两点已经连通，检查该子树中值最小的边，如果比当前边小，那么删去并加入当前边。
    • 如果不连通，直接加入这条边。
  • 复杂度 \(O(n \log n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxm = 5E5 + 5E3 + 100, maxn = 5E3 + 100;
const int INF = 1E9;

namespace lct {
    extern struct P* null;
    struct P {
        P *fa, *ls, *rs;
        int v;
        P *minp;
        bool rev;

        bool has_fa() { return fa->ls == this || fa->rs == this; }
        bool d() { return fa->ls == this; }
        P*& c(bool x) { return x ? ls : rs; }
        void do_rev() { if (this == null) return; rev ^= 1; swap(ls, rs); }

        P* up() {
            minp = this;
            if (minp->v > ls->minp->v) minp = ls->minp;
            if (minp->v > rs->minp->v) minp = rs->minp;
            return this;
        }
        void down() { if (rev) { rev = 0; ls->do_rev(); rs->do_rev(); }}
        void all_down() { if (has_fa()) fa->all_down(); down(); }
    } *null = new P{0, 0, 0, INF, 0, 0}, pool[maxm], *pit = pool;
    void rot(P* o) {
        bool dd = o->d();
        P *f = o->fa, *t = o->c(!dd);
        if (f->has_fa()) f->fa->c(f->d()) = o; o->fa = f->fa;
        if (t != null) t->fa = f; f->c(dd) = t;
        o->c(!dd) = f->up(); f->fa = o;
    }
    void splay(P* o) {
        o->all_down();
        while (o->has_fa()) {
            if (o->fa->has_fa()) rot(o->d() ^ o->fa->d() ? o : o->fa);
            rot(o);
        }
        o->up();
    }
    void access(P* u, P* v = null) {
        if (u == null) return;
        splay(u); u->rs = v;
        access(u->up()->fa, u);
    }
    void make_root(P* o) { access(o); splay(o); o->do_rev(); }
    void split(P* u, P* v) { make_root(u); access(v); splay(v); }
    bool linked(P* u, P* v) { split(u, v); return u == v || u->fa != null; }
    void link(P* u, P* v) { make_root(u); u->fa = v; }
    void cut(P* u, P* v) { split(u, v); u->fa = v->ls = null; v->up(); }
}

using namespace lct;
int n, m;
P *p[maxn];
struct Q {
    int tp, u, v, l, r;
};
vector<Q> q;

int main() {
    null->minp = null;
    cin >> n >> m;
    FOR (i, 1, n + 1) p[i] = new (pit++) P{null, null, null, INF, p[i], 0};
    int clk = 0;
    map<pair<int, int>, int> mp;
    FOR (_, 0, m) {
        int tp, u, v; scanf("%d%d%d", &tp, &u, &v);
        if (u > v) swap(u, v);
        if (tp == 0) mp.insert({{u, v}, clk});
        else if (tp == 1) {
            auto it = mp.find({u, v}); assert(it != mp.end());
            q.push_back({1, u, v, it->second, clk});
            mp.erase(it);
        } else q.push_back({0, u, v, clk, clk});
        ++clk;
    }
    for (auto& x: mp) q.push_back({1, x.first.first, x.first.second, x.second, clk});
    sort(q.begin(), q.end(), [](const Q& a, const Q& b)->bool { return a.l < b.l; });
    map<P*, int> mp2;
    FOR (i, 0, q.size()) {
        Q& cur = q[i];
        int u = cur.u, v = cur.v;
        if (cur.tp == 0) {
            if (!linked(p[u], p[v])) puts("N");
            else puts(p[v]->minp->v >= cur.r ? "Y" : "N");
            continue;
        }
        if (linked(p[u], p[v])) {
            P* t = p[v]->minp;
            if (t->v > cur.r) continue;
            Q& old = q[mp2[t]];
            cut(p[old.u], t); cut(p[old.v], t);
        }
        P* t = new (pit++) P {null, null, null, cur.r, t, 0};
        mp2[t] = i;
        link(t, p[u]); link(t, p[v]);
    }
}