All-Star Game - 题解

标签与难度

标签: 数据结构, 并查集, 可撤销并查集, 线段树分治, 离线算法, 图论 难度: 2500

题目大意喵~

哈喵~ 各位算法大师们好呀！今天我要带大家攻略一道关于篮球全明星赛的有趣问题，喵~

是这样的说：在一个国家里有 $n$ 位篮球运动员和 $m$ 位篮球迷。 一位球迷 $i$ "喜欢看" 某位球员 $j$ 的比赛，这个关系是可以传递的哦！规则如下：

1. 如果球迷 $i$ 本身就是球员 $j$ 的粉丝，那他肯定喜欢看 $j$ 的比赛。
2. 如果存在一个中介球迷 $i'$ 和一个中介球员 $j'$，满足：球迷 $i$ 和球迷 $i'$ 都喜欢看球员 $j'$ 的比赛，并且球迷 $i'$ 还喜欢看球员 $j$ 的比赛，那么球迷 $i$ 也会喜欢上看球员 $j$ 的比赛。

现在要举办全明星赛，我们需要挑选一部分球员参加。一个球迷只要喜欢看的球员中至少有一位被选中，他就会去观看比赛。我们的目标是，用最少的球员，让所有球迷都来观看比赛。

更刺激的是，这道题还有 $q$ 次动态修改！每次修改会增加或删除一对 "球迷-球员" 的粉丝关系。在每次修改之后，我们都需要回答当前状态下，最少需要挑选多少球员。如果无论如何都无法满足所有球迷，就要输出 "-1" 呐。

解题思路分析

喵哈~ 这道题看起来关系错综复杂，还有动态修改，真是对我智慧的挑战呢！不过别怕，跟着我的思路一步步来，就能把这只“纸老虎”拿下~

1. "喜欢看"关系的本质是什么喵？

首先，我们来分析一下那个看起来有点绕的 "喜欢看" 的定义。我们可以把球员和球迷都看作图上的节点。如果球迷 $i$ 是球员 $j$ 的粉丝，我们就在他们之间连一条边。

那么 "喜欢看" 关系到底是什么呢？

• "球迷 $i$ 和球迷 $i'$ 都喜欢看球员 $j'$ 的比赛" -> 这意味着 $i$ 和 $j'$ 连通，$i'$ 和 $j'$ 也连通。
• "球迷 $i'$ 喜欢看球员 $j$ 的比赛" -> 这意味着 $i'$ 和 $j$ 连通。

如果这些条件都满足，那么 $i, i', j, j'$ 实际上都在同一个连通块里。所以，结论就是：球迷 $i$ "喜欢看" 球员 $j$ 的比赛，当且仅当他们在我们构建的图中处于同一个连通块里。

2. 如何满足所有球迷？

我们的目标是用最少的球员满足所有球迷。对于一个包含了一群球迷和一群球员的连通块，我们只要从这个块里随便挑选一个球员，这个连通块里的所有球迷就都被满足了，因为他们都和这个被选中的球员连通！

所以，我们的策略就清晰了：

• 找出图中所有的连通块。
• 对于每个包含至少一个球迷的连通块，我们必须从中挑选一名球员。
• 为了使总数最少，我们只为每个这样的连通块挑选一名球员。

那么，最少需要的球员数量，就是包含球迷的连通块的数量。

但是，如果某个连通块里只有球迷，没有球员怎么办？那就糟糕了，我们无法从这个块里挑选球员来满足他们，任务就无法完成了。这种情况对应着输出 "-1"。

所以，最终的答案是：

• 如果存在一个只包含球迷的连通块，则输出 "-1"。
• 否则，答案就是包含球迷和球员的混合连通块的数量。

3. 应对动态修改：离线大法好！

这道题的棘手之处在于有 $q$ 次修改，而且修改既有增加关系，也有删除关系。我们都知道，并查集（DSU）处理合并（加边）非常快，但处理删除（删边）就很麻烦。

当遇到不好处理的删除操作时，一个经典的思路就是离线处理！我们可以把所有操作看作是在一个时间轴上发生的。每一对 "球迷-球员" 关系，都有它的"生命周期"，也就是它存在的时间区间 [t_start, t_end]。

• 初始就有的关系，生命周期是 [1, q]。
• 在第 i 次查询时增加的关系，它的生命周期从 i 开始。如果它后来在第 j 次查询时被删除了，那么它的生命周期就是 [i, j-1]；如果它一直没被删除，生命周期就是 [i, q]。

4. 线段树分治 + 可撤销并查集

有了每个关系的生命周期，我们就可以使用 线段树分治 这个强大的技巧了！

1. 建立时间线段树：我们建立一棵线段树，其叶子节点代表时间点 $1, 2, \dots, q$。树中的每个节点都代表一个时间区间。

2. 关系挂载：对于每个关系的生命周期 [t_start, t_end]，我们把它“挂”到线段树上覆盖这个区间的若干个节点上。这和普通的线段树区间更新是一样的操作。

3. DFS 遍历线段树：我们从根节点开始对线段树进行深度优先搜索（DFS）。

   • 进入节点：当我们进入一个代表区间 [L, R] 的节点时，我们将挂载在该节点上的所有关系（边）用并查集连接起来。
   • 到达叶子：如果走到了叶子节点（L == R），此时并查集的状态就正好是第 L 次查询结束后的状态。我们就在这里计算并输出答案。
   • 离开节点：当我们离开一个节点（即处理完它的子树）时，我们需要撤销进入该节点时所做的所有合并操作，恢复并查集到进入之前的状态。这样才能保证在处理兄弟节点时状态是正确的。

为了实现撤销，我们需要一个可撤销并查集。普通的带路径压缩的并查集很难撤销，所以我们使用不带路径压缩、只按秩（或大小）合并的并查-集，并用一个栈来记录每次合并前的状态，以便回溯。

5. 快速计算答案

在DFS到每个叶子节点时，我们如何快速计算答案呢？如果在叶子节点再遍历所有节点来统计连通块类型，那也太慢了 (O(n+m))！

我们可以维护三个计数器，并在并查集合并时动态更新它们！

• count_P_only: 只包含球员的连通块数量。
• count_F_only: 只包含球迷的连通块数量。
• count_PF: 既有球员又有球迷的混合连通块数量。

初始时，有 n 个球员，m 个球迷，所以 count_P_only = n, count_F_only = m, count_PF = 0。

当合并两个连通块 u 和 v 时，根据它们的类型，计数器会发生如下变化：

• P + P -> P: count_P_only 减 1。
• F + F -> F: count_F_only 减 1。
• P + F -> PF: count_P_only 减 1, count_F_only 减 1, count_PF 加 1。
• P + PF -> PF: count_P_only 减 1。
• F + PF -> PF: count_F_only 减 1。
• PF + PF -> PF: count_PF 减 1。

这些计数器的变化也要记录在我们的回滚栈里！这样，在DFS的每个叶子节点，我们只需 O(1) 的时间就能通过 count_F_only 和 count_PF 得出答案啦！

总结一下我们的屠龙之术： 离线处理所有操作 -> 计算每个关系的存在时间区间 -> 线段树分治 -> 将关系区间挂载到线段树上 -> DFS遍历线段树，用可撤销并查集（带计数器）维护状态 -> 在叶子节点输出答案。

是不是感觉思路清晰多了，喵~

代码实现

下面是我根据上面的思路，精心重构的一份代码，注释超详细的哦，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <stack>
#include <utility>

// 为了方便，我们给球员和球迷重新编号
// 球员 j (1-n) -> 节点 j (1-n)
// 球迷 i (1-m) -> 节点 n+i (n+1 - n+m)
const int MAXN_PLAYERS = 200005;
const int MAXN_FANS = 200005;
const int MAX_NODES = MAXN_PLAYERS + MAXN_FANS;
const int MAX_QUERIES = 200005;

// 可撤销并查集的数据结构
int parent[MAX_NODES];
int component_size[MAX_NODES];
bool has_player[MAX_NODES];
bool has_fan[MAX_NODES];

// 用于计算答案的计数器
long long count_P_only; // 只含球员的连通块
long long count_F_only; // 只含球迷的连通块
long long count_PF;     // 混合连通块

// 撤销操作的历史记录栈
// pair<int*, int> 记录了某个地址在修改前的值
std::stack<std::pair<int*, int>> history;
// 记录计数器修改前的状态
std::stack<std::tuple<long long, long long, long long>> counter_history;

// 线段树，用于挂载边的生命周期
std::vector<std::pair<int, int>> time_segment_tree[4 * MAX_QUERIES];

// DSU find 操作，不使用路径压缩以方便撤销
int find_set(int v) {
    while (v != parent[v]) {
        v = parent[v];
    }
    return v;
}

// 记录一个变量的旧值
void save_value(int* addr) {
    history.push({addr, *addr});
}

// DSU union 操作，核心逻辑
void unite_sets(int u, int v) {
    int root_u = find_set(u);
    int root_v = find_set(v);

    if (root_u != root_v) {
        // 按大小合并，小的合并到大的上面
        if (component_size[root_u] < component_size[root_v]) {
            std::swap(root_u, root_v);
        }

        // 保存计数器和DSU状态，以便回滚
        counter_history.push({count_P_only, count_F_only, count_PF});
        save_value(&parent[root_v]);
        save_value(&component_size[root_u]);
        save_value((int*)&has_player[root_u]);
        save_value((int*)&has_fan[root_u]);

        // --- 更新计数器 ---
        bool u_is_P = has_player[root_u] && !has_fan[root_u];
        bool u_is_F = !has_player[root_u] && has_fan[root_u];
        bool v_is_P = has_player[root_v] && !has_fan[root_v];
        bool v_is_F = !has_player[root_v] && has_fan[root_v];

        if (u_is_P && v_is_P) count_P_only--;
        else if (u_is_F && v_is_F) count_F_only--;
        else if ((u_is_P && v_is_F) || (u_is_F && v_is_P)) {
            count_P_only--;
            count_F_only--;
            count_PF++;
        } else if ((u_is_P && !v_is_P && !v_is_F) || (v_is_P && !u_is_P && !u_is_F)) {
            count_P_only--;
        } else if ((u_is_F && !v_is_P && !v_is_F) || (v_is_F && !u_is_P && !u_is_F)) {
            count_F_only--;
        } else { // PF + PF
            count_PF--;
        }
        
        // --- 执行合并 ---
        parent[root_v] = root_u;
        component_size[root_u] += component_size[root_v];
        has_player[root_u] = has_player[root_u] || has_player[root_v];
        has_fan[root_u] = has_fan[root_u] || has_fan[root_v];
    }
}

// 撤销操作
void rollback(size_t checkpoint_size, size_t counter_checkpoint_size) {
    while (history.size() > checkpoint_size) {
        auto [addr, val] = history.top();
        history.pop();
        *addr = val;
    }
    while (counter_history.size() > counter_checkpoint_size) {
        auto [cp, cf, cpf] = counter_history.top();
        counter_history.pop();
        count_P_only = cp;
        count_F_only = cf;
        count_PF = cpf;
    }
}

// 将边的生命周期 [start, end] 添加到线段树
void add_edge_to_segtree(int node, int L, int R, int start, int end, std::pair<int, int> edge) {
    if (start > end || L > R || start > R || end < L) {
        return;
    }
    if (start <= L && R <= end) {
        time_segment_tree[node].push_back(edge);
        return;
    }
    int mid = L + (R - L) / 2;
    add_edge_to_segtree(2 * node, L, mid, start, end, edge);
    add_edge_to_segtree(2 * node + 1, mid + 1, R, start, end, edge);
}

// DFS 遍历线段树求解
void solve_dfs(int node, int L, int R) {
    // 记录进入此节点前的状态点
    size_t checkpoint = history.size();
    size_t counter_checkpoint = counter_history.size();

    // 应用当前时间区间的边
    for (const auto& edge : time_segment_tree[node]) {
        unite_sets(edge.first, edge.second);
    }

    if (L == R) {
        // 到达叶子节点，计算并输出当前时间的答案
        if (count_F_only > 0) {
            printf("-1\n");
        } else {
            printf("%lld\n", count_PF);
        }
    } else {
        int mid = L + (R - L) / 2;
        solve_dfs(2 * node, L, mid);
        solve_dfs(2 * node + 1, mid + 1, R);
    }

    // 离开此节点，回滚所有修改
    rollback(checkpoint, counter_checkpoint);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    // 初始化并查集和计数器
    for (int i = 1; i <= n + m; ++i) {
        parent[i] = i;
        component_size[i] = 1;
        has_player[i] = (i <= n);
        has_fan[i] = (i > n);
    }
    count_P_only = n;
    count_F_only = m;
    count_PF = 0;

    // 记录边的出现时间
    std::map<std::pair<int, int>, int> edge_start_time;

    // 处理初始边
    for (int j = 1; j <= n; ++j) {
        int k;
        scanf("%d", &k);
        for (int l = 0; l < k; ++l) {
            int i;
            scanf("%d", &i);
            edge_start_time[{n + i, j}] = 1; // 初始边从时间点1开始
        }
    }

    // 处理q次查询
    for (int t = 1; t <= q; ++t) {
        int i, j;
        scanf("%d %d", &i, &j);
        std::pair<int, int> edge = {n + i, j};
        if (edge_start_time.count(edge)) {
            // 边被删除，确定其生命周期并加入线段树
            int start_time = edge_start_time[edge];
            add_edge_to_segtree(1, 1, q, start_time, t - 1, edge);
            edge_start_time.erase(edge);
        } else {
            // 边被添加，记录其开始时间
            edge_start_time[edge] = t;
        }
    }

    // 处理到最后仍然存在的边
    for (auto const& [edge, start_time] : edge_start_time) {
        add_edge_to_segtree(1, 1, q, start_time, q, edge);
    }
    
    // 如果q=0，需要特殊处理
    if (q == 0) {
        // 在q=0时，只有初始边。我们手动合并它们。
        for (auto const& [edge, start_time] : edge_start_time) {
            unite_sets(edge.first, edge.second);
        }
        if (count_F_only > 0) {
            // 题目保证q>=1，但以防万一
        } else {
            // 题目没有q=0的情况，所以此分支通常不会执行
        }
    } else {
        solve_dfs(1, 1, q);
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(K \log q \log(n+m))$

  • $K$ 是问题中出现过的所有不同 "球迷-球员" 关系的总数。
  • 每个关系最多被添加和删除一次，所以它在时间轴上形成若干个区间。每个区间会被分解成 $O(\log q)$ 个线段树节点。
  • 因此，所有关系总共会被挂载到线段树上 $O(K \log q)$ 次。
  • 每次挂载（即DFS中处理边）会调用一次并查集的 unite_sets 操作。由于我们没有使用路径压缩，find_set 的复杂度是 $O(\log N)$，其中 $N = n+m$ 是节点总数。
  • 所以总时间复杂度是 $O(K \log q \log(n+m))$ 呐。

• 空间复杂度: $O(K \log q + n + m)$

  • 线段树需要存储所有挂载的边，空间为 $O(K \log q)$。
  • 并查集本身需要 $O(n+m)$ 的空间。
  • 撤销栈的深度与DFS深度（$O(\log q)$）和每层节点上的边数有关，最大空间也约为 $O(K \log q)$。

知识点总结

这道题是数据结构组合拳的绝佳练习，喵~

1. 问题建模: 将复杂的文字描述转化为清晰的图论模型（连通性问题）是解题的第一步。
2. 离线思想: 当在线算法难以处理动态删除操作时，考虑将所有查询读入后统一处理，将问题从动态转化为静态。
3. 线段树分治: 这是处理带时间区间的操作的利器。它巧妙地将每个操作的影响范围分配到时间轴线段树的节点上，通过一次DFS遍历完成所有时间点的查询。
4. 可撤销并查集 (DSU with Rollback): 为了配合线段树分治，我们需要一个能够“回到过去”的数据结构。通过放弃路径压缩，并使用栈记录历史状态，我们可以实现高效的撤销操作。
5. 增量计算与状态维护: 在并查集中额外维护 has_player, has_fan 等属性，以及全局的 count_P_only, count_F_only, count_PF 计数器，使得在每个查询点都能 $O(1)$ 计算答案，这是优化的关键。

希望这篇题解能让你对这些强大的算法有更深的理解！下次再一起挑战难题吧，喵~