题解：P11519 [CCO 2024] Telephone Plans

· · 题解

提供两种做法。

题意

维护 3 种操作：

保证每条边只被添加删除一次，强制在线。

解法

注意“保证每条边只被添加删除一次”这个信息，那么答案即为 [1, s] 间的操作添加的点对数减去 [1, s - t] 间删除的点对数，只需要在线维护每次操作添加 / 删除的点对数即可。

维护方法 1

使用启发式合并/分裂。具体地，直接维护整个图，合并时暴力将小的连通块合并到大的连通块里；分裂时同时拓展两个连通块，如果其中一个连通块拓展完了，说明这个连通块较小，得到它的大小后就不用计算另外一个连通块的大小了。显然，分裂/合并的复杂度都是 \mathcal{O}(\min\{\operatorname{size}(u), \operatorname{size}(v)\}) 的，其中 \operatorname{size}(\cdot) 是连通块大小。可以证明总复杂度是 \mathcal{O}(n \log n) 的。

细节上，bfs 拓展时要记录邻接表的迭代器，不能每次都遍历一个点的边集，否则会被类菊花图卡掉。

维护方法 2

使用 LCT 维护，对每个节点额外维护虚子树的大小，access 和 link 时修改即可。

复杂度和启发式合并 / 分裂一样，但是常数小得多，跑得很快。

代码

:::success[启发式合并 / 分裂]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll N = 5e5 + 5, Q = 1.5e6 + 5;

int E, n, q, cnt, blg[N];
set<int> g[N], pts[N << 1];
ll del[Q], sum;
int vis[N], T;
using SI = set<int>::iterator;
using TS = tuple<int, int, SI>;

ll merge(int u, int v) {
    g[u].emplace(v), g[v].emplace(u);
    int bu = blg[u], bv = blg[v];
    if (bu == bv) return 0;
    if (pts[bu].size() < pts[bv].size()) swap(u, v), swap(bu, bv);
    const ll res = pts[bu].size() * pts[bv].size();
    for (const int x : pts[bv]) {
        blg[x] = bu;
        pts[bu].insert(x);
    }
    pts[bv].clear();
    return res;
}

ll split(const int u, const int v) {
    g[u].erase(v), g[v].erase(u), ++T;
    vector<int> p[2];
    queue<TS> q[2];
    const auto push = [&](const int i, const int x, const int y) {
        p[i].emplace_back(x);
        vis[x] = T;
        if (!g[x].empty()) q[i].emplace(y, x, g[x].begin());
    };
    push(0, u, 0), push(1, v, 0);
    while (!q[0].empty() && !q[1].empty()) {
        for (int i = 0; i <= 1; ++i) {
            if (q[i].empty()) continue;
            const int z = get<0>(q[i].front()), x = get<1>(q[i].front());
            auto it = get<2>(q[i].front()); q[i].pop();
            if (it == g[x].end()) continue;
            if (vis[*it] != T) push(i, *it, x);
            ++it;
            if (it == g[x].end()) continue;
            if (*it == z) ++it;
            if (it == g[x].end()) continue;
            q[i].emplace(z, x, it);
        }
    }
    const int s = q[1].empty();
    ++cnt;
    const int bu = blg[u];
    const ll res = p[s].size() * (pts[bu].size() - p[s].size());
    for (const int x : p[s]) {
        pts[bu].erase(x);
        pts[cnt].emplace(x);
        blg[x] = cnt;
    }
    return res;
}

signed main() {
    cin >> E >> n >> q;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) blg[cnt = i] = i, pts[i].emplace(i);
    for (int s = 1; s <= q; ++s) {
        del[s] = del[s - 1];
        ll op;
        cin >> op;
        if (op == 3) {
            ll t;
            cin >> t;
            if (E) t ^= ans;
            cout << (ans = sum - del[s - t]) << '\n';
        } else {
            ll x, y;
            cin >> x >> y;
            if (E) x ^= ans, y ^= ans;
            if (op == 1) sum += merge(x, y);
            else del[s] += split(x, y);
        }
    }
    return 0;
}

:::

:::success[LCT]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll N = 5e5 + 5, Q = 1.5e6 + 5;

struct LCT {
    struct node { int son[2], fa, rev, siz, vir; } st[N];
#define ls(rt) (st[(rt)].son[0])
#define rs(rt) (st[(rt)].son[1])
#define fa(rt) (st[(rt)].fa)
    bool dir(const int rt) const { return rs(fa(rt)) == rt; }
    bool is_root(const int rt) const { return ls(fa(rt)) != rt && rs(fa(rt)) != rt; }
    void reverse(const int rt) { if (rt) st[rt].rev ^= 1, swap(ls(rt), rs(rt)); }
    void pushdown(const int rt) { if (st[rt].rev) st[rt].rev ^= 1, reverse(ls(rt)), reverse(rs(rt)); }
    void pushup(const int rt) { if (rt) st[rt].siz = st[ls(rt)].siz + st[rs(rt)].siz + st[rt].vir + 1; }
    void update(const int rt) { if (!is_root(rt)) update(fa(rt)); pushdown(rt); }
    void rotate(const int rt) {
        const int y = fa(rt), z = fa(y);
        const bool d = dir(rt);
        st[y].son[d] = st[rt].son[!d];
        if (st[rt].son[!d]) fa(st[rt].son[!d]) = y;
        if (!is_root(y)) st[z].son[dir(y)] = rt;
        fa(rt) = z;
        st[rt].son[!d] = y, fa(y) = rt;
        pushup(y), pushup(rt);
    }
    void splay(const int rt) {
        update(rt);
        for (int y; y = fa(rt), !is_root(rt); rotate(rt)) if (!is_root(y)) rotate(dir(rt) == dir(y) ? y : rt);
    }
    void access(int rt) {
        for (int y = 0; rt; y = rt, rt = fa(rt)) {
            splay(rt);
            if (rs(rt)) st[rt].vir += st[rs(rt)].siz;
            rs(rt) = y;
            if (y) st[rt].vir -= st[y].siz;
            pushup(rt);
        }
    }
    void make_root(const int rt) { access(rt), splay(rt), reverse(rt); }
    int find(int rt) {
        access(rt), splay(rt);
        while (ls(rt)) pushdown(rt), rt = ls(rt);
        splay(rt);
        return rt;
    }
    void split(const int u, const int v) { make_root(u), access(v), splay(v); }
    void link(const int u, const int v) {
        make_root(u);
        if (find(v) != u) {
            make_root(v);
            st[u].vir += st[v].siz;
            fa(v) = u;
            pushup(u);
        }
    }
    void cut(const int u, const int v) {
        if (find(u) != find(v)) return;
        split(u, v);
        if (ls(v) != u || rs(u)) return;
        ls(v) = fa(u) = 0, pushup(v);
    }
    int size(const int rt) { make_root(rt); return st[rt].siz; }
#undef ls
#undef rs
#undef fa
} lct;

int E, n, q;
ll del[Q], sum, ans;

ll merge(const int u, const int v) { const ll r = 1ll * lct.size(u) * lct.size(v); lct.link(u, v); return r; }
ll split(const int u, const int v) { lct.cut(u, v); return 1ll * lct.size(u) * lct.size(v); }

signed main() {
    cin >> E >> n >> q;
    for (int s = 1; s <= q; ++s) {
        del[s] = del[s - 1];
        ll op;
        cin >> op;
        if (op == 3) {
            ll t;
            cin >> t;
            if (E) t ^= ans;
            cout << (ans = sum - del[s - t]) << '\n';
        } else {
            ll x, y;
            cin >> x >> y;
            if (E) x ^= ans, y ^= ans;
            if (op == 1) sum += merge(x, y);
            else del[s] += split(x, y);
        }
    }
    return 0;
}

:::