「CCO 2024」Telephone Plans 题解

题目分析

本题需要维护一个动态森林（无环图），支持加边、删边操作，并回答查询：在最近 $t+1$ 个版本中至少有一个版本连通的点对数量。

核心思路

关键观察

设当前版本为 $i$，查询要求计算在版本 $[i-t, i]$ 中至少一个版本连通的点对数。这等价于：

当前连通的点对数 - 在整个 $[i-t, i]$ 期间都不连通的点对数

但更巧妙的做法是：维护当前连通点对数 $cur$ 和历史删除边导致的连通点对减少量 $sdel$，那么答案为：

其中 $sdel[i]$ 表示前 $i$ 次操作中因删边而减少的连通点对总数。

算法设计

1. 动态维护连通分量

   • 使用类似并查集的结构，但支持快速拆分
   • 每个连通分量用一棵树表示，节点间用邻接表连接

2. 加边操作

   • 合并两个连通分量时，选择较小的分量合并到较大的分量（类似按秩合并）
   • 更新当前连通点对数：$cur += size[u] \times size[v]$

3. 删边操作

   • 从邻接表中删除边后，需要确定哪些节点属于新的两个连通分量
   • 使用双向BFS从两个端点出发探索，找到较小的连通分量
   • 计算因此次删边减少的连通点对数，累加到 $sdel$ 数组中

代码实现详解

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5, M = 3e6 + 5;
using Iter = unordered_set<int>::iterator;

unordered_set<int> e[N];  // 邻接表存储图
int siz[M], cur, sdel[M], dcnt;  // siz:分量大小, cur:当前连通对数, sdel:删除累计, dcnt:分量计数器

// 可恢复标记数组，用于BFS时记录访问节点
struct RestorableArray {
    bool tmp[N];
    stack<int> modified;
    void set(int x) {
        modified.push(x);
        tmp[x] = true;
    }
    bool check(int x) {
        return tmp[x];
    }
    void clear() {
        while (!modified.empty())
            tmp[modified.top()] = false, modified.pop();
    }
} vis;

// 并查集结构，维护节点所属连通分量
struct DisjointSet {
    int fa[M];
    void getready(int n) {
        dcnt = n + n;  // 初始分配2n个分量
        for (int i = 1; i <= n; i++)
            fa[i] = i + n, fa[i + n] = i + n, siz[i + n] = 1;
    }
    int get(int x) {
        return (fa[x] == x ? x : (fa[x] = get(fa[x])));
    }
    int operator[](int x) {
        return get(x);
    }
} bel;

// 加边操作
void AddLink(int x, int y) {
    if (siz[bel[x]] > siz[bel[y]])
        swap(x, y);  // 保证x所在分量较小
    
    // 更新连通点对数
    cur += siz[bel[x]] * siz[bel[y]];
    siz[bel[y]] += siz[bel[x]];  // 更新分量大小
    
    // BFS将小分量中所有节点合并到大分量
    queue<int> q;
    q.push(x), vis.set(x);
    while (!q.empty()) {
        int ln = q.front();
        q.pop();
        bel.fa[ln] = bel[y];  // 修改节点所属分量
        for (int v : e[ln])
            if (!vis.check(v))
                vis.set(v), q.push(v);
    }
    vis.clear();
    
    // 在邻接表中添加边
    e[x].insert(y), e[y].insert(x);
}

// 删边操作，返回因此减少的连通点对数
int DelLink(int x, int y) {
    e[x].erase(y), e[y].erase(x);  // 从邻接表删除边
    
    // 双向BFS确定新的两个连通分量
    vector<int> L, R;  // 存储两个新分量的节点
    queue<pair<int, Iter>> lq, rq;  // BFS队列，存储节点和当前邻接表迭代器
    
    lq.push(make_pair(x, e[x].begin())), L.push_back(x), vis.set(x);
    rq.push(make_pair(y, e[y].begin())), R.push_back(y), vis.set(y);
    
    bool flg1 = true, flg2 = true;
    while (flg1 and flg2) {  // 交替扩展直到一方无法扩展
        flg1 = flg2 = false;
        
        // 扩展左侧分量
        while (!lq.empty()) {
            auto &[x, it] = lq.front();
            while (it != e[x].end() and vis.check(*it))
                it++;  // 跳过已访问节点
            if (it == e[x].end()) {
                lq.pop();
                continue;
            }
            vis.set(*it), L.push_back(*it), flg1 = true;
            lq.push(make_pair(*it, e[*it].begin())), it++;
            break;
        }
        
        // 扩展右侧分量
        while (!rq.empty()) {
            auto &[x, it] = rq.front();
            while (it != e[x].end() and vis.check(*it))
                it++;  // 跳过已访问节点
            if (it == e[x].end()) {
                rq.pop();
                continue;
            }
            vis.set(*it), R.push_back(*it), flg2 = true;
            rq.push(make_pair(*it, e[*it].begin())), it++;
            break;
        }
    }
    
    int res = 0, osz = siz[bel[x]];  // 原分量大小
    
    // 根据哪边先停止扩展，确定较小的分量
    if (!flg1) {  // 左侧是较小分量
        // 创建新分量给左侧节点
        siz[++dcnt] = L.size(), bel.fa[dcnt] = dcnt;
        for (int i : L) bel.fa[i] = dcnt;
        
        // 剩余节点保持原分量
        siz[++dcnt] = osz - L.size(), bel.fa[dcnt] = dcnt;
        bel.fa[bel[y]] = dcnt;  // 更新原分量标识
        
        res = 1ll * L.size() * siz[bel[y]];  // 计算减少的连通对数
    } else {  // 右侧是较小分量
        siz[++dcnt] = R.size(), bel.fa[dcnt] = dcnt;
        for (int i : R) bel.fa[i] = dcnt;
        
        siz[++dcnt] = osz - R.size(), bel.fa[dcnt] = dcnt;
        bel.fa[bel[x]] = dcnt;
        
        res = 1ll * R.size() * siz[bel[x]];
    }
    
    vis.clear();
    return res;
}

int n, E, q, lstans;
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> E >> n >> q;
    bel.getready(n);  // 初始化并查集
    
    for (int i = 1; i <= q; i++) {
        int op, x, y;
        cin >> op;
        sdel[i] = sdel[i - 1];  // 继承之前的删除累计
        
        if (op == 1) {  // 加边
            cin >> x >> y;
            x ^= lstans * E, y ^= lstans * E;  // 处理加密
            AddLink(x, y);
        } else if (op == 2) {  // 删边
            cin >> x >> y;
            x ^= lstans * E, y ^= lstans * E;
            sdel[i] += DelLink(x, y);  // 累加删除影响
        } else {  // 查询
            cin >> x;
            x ^= lstans * E;
            // 核心公式：当前连通对数 - t版本前的删除影响
            lstans = cur - sdel[i - x];
            cout << lstans << "\n";
        }
    }
}

复杂度分析

• 加边操作：$O(\min(size_u, size_v))$，均摊 $O(\log n)$
• 删边操作：$O(\min(size_u, size_v))$，找到较小连通分量
• 查询操作：$O(1)$
• 总复杂度：$O((n+q)\log n)$

总结

本题通过巧妙维护当前连通点对数和历史删除影响，将复杂的时间窗口查询转化为简单的差值计算。核心在于高效维护动态连通分量，并在删边时快速确定新的连通情况。