题解：Phone Plans

题目分析

问题核心

给定 (N) 个住户、(A) 条 K 公司电话线、(B) 条 C 公司电话线，需从两家公司各购买一个等级套餐（价格=等级），使得至少有 (K) 对住户能通过任意一家公司的电话线连通（不重复计数），求套餐总价格的最小值。若无法满足则输出 (-1)。

关键约束与公式

1. 连通对数计算：若一个连通分量有 (s) 个住户，其内部连通对数为组合数 (\binom{s}{2} = \frac{s(s-1)}{2})。
2. 不重复计数：总连通对数 = K 公司连通对数 + C 公司连通对数 - 两家公司共同连通的对数（即同一对住户通过两家公司均能连通的情况）。
3. 套餐规则：购买等级 (l) 的套餐可使用该公司所有等级 ≤ (l) 的电话线，价格为 (l)，需最小化总价格 (l_K + l_C)。

数据范围挑战

• (N, A, B \leq 2 \times 10^5)，需 (O((A+B)\log(A+B))) 复杂度算法，避免暴力枚举。
• 核心难点：高效计算“两家公司共同连通的对数”，并快速找到满足条件的最小总价格。

算法设计

核心思路

采用“枚举 K 公司套餐等级 + 双指针维护 C 公司套餐等级”的策略，结合并查集（Union-Find）维护连通分量，核心步骤如下：

1. 预处理 K 公司：按电话线等级升序排序，用并查集逐步合并连通分量，记录每个等级对应的总连通对数，以及合并过程的“撤销信息”（用于回溯）。
2. 双指针维护 C 公司：按电话线等级升序排序，枚举 K 公司的所有可能套餐等级（从高到低），用双指针逐步提升 C 公司套餐等级，确保总连通对数 ≥ (K)，并记录最小总价格。
3. 去重计算：通过哈希表维护 C 公司连通分量中各住户在 K 公司的连通归属，快速计算两家公司共同连通的对数，确保总对数计算准确。

具体步骤

1. 预处理 K 公司（正向并查集 + 记录信息）

• 排序：将 K 公司的电话线按等级升序排序。
• 并查集合并：按等级分组合并连通分量（同一等级的电话线一起处理），记录：
  • (aval[i])：第 (i) 组的等级（即 K 公司套餐等级）。
  • (anum[i])：前 (i) 组合并后的总连通对数（K 公司单独的连通对数）。
  • (asp[i])：第 (i) 组合并的父节点信息（用于后续回溯）。
  • (abl[i])：每个连通分量的住户列表（用于回溯时恢复归属）。

2. 初始化 C 公司与去重统计

• 排序：将 C 公司的电话线按等级升序排序。
• 并查集与哈希表：初始化 C 公司的并查集，用哈希表 (mp[x][y]) 记录 C 公司连通分量 (x) 中，属于 K 公司连通分量 (y) 的住户数量。
• 共同对数计算：定义 (Y) 为两家公司共同连通的对数，初始时 (Y = \sum \binom{mp[x][y]}{2})（即同一 C 分量中，属于同一 K 分量的住户对）。

3. 双指针枚举与回溯（核心步骤）

• 枚举 K 公司等级：从最高等级组开始，逐步回溯到最低等级（通过 (asp[i]) 恢复 K 公司的连通分量）。
• 双指针提升 C 等级：对于当前 K 公司的总连通对数 (anum[i])，逐步加入 C 公司的电话线（提升 C 套餐等级），直到总连通对数 (anum[i] + X - Y \geq K)（(X) 为 C 公司单独的连通对数）。
• 计算最小总价格：若满足条件，更新最小总价格 (aval[i] + b[pos-1].z)（(b[pos-1].z) 为当前 C 公司套餐等级）。

4. 回溯 K 公司连通分量

• 当 K 公司从等级组 (i) 回溯到 (i-1) 时，需恢复之前合并的连通分量，并更新 (Y)（共同连通对数）：
  • 将合并的分量拆分，恢复住户在 K 公司的归属（(bel[k])）。
  • 重新计算哈希表 (mp) 和 (Y)，确保后续统计准确。

代码关键模块解析

1. 并查集与预处理 K 公司

// 并查集查找（路径压缩）
int find(int x) { return fa[x] == x ? x : find(fa[x]); }

// 预处理 K 公司：按等级分组合并，记录信息
sort(a + 1, a + A + 1); // K 公司电话线按等级升序排序
for (int i = 1; i <= A; i++) {
    int r = i;
    while (r <= A && a[i].z == a[r].z) r++; // 同一等级的电话线分组
    r--, alen++;
    anum[alen] = anum[alen - 1], aval[alen] = a[i].z;
    for (int j = i; j <= r; j++) {
        int x = find(a[j].x), y = find(a[j].y);
        if (x == y) continue;
        // 累加 K 公司连通对数（合并两个分量的新增对数）
        anum[alen] += abl[x].size() * abl[y].size();
        if (abl[x].size() > abl[y].size()) swap(x, y);
        // 合并分量，记录撤销信息
        for (int k : abl[x]) abl[y].push_back(k);
        fa[x] = y, asp[alen].push_back(x);
    }
    i = r;
}

• 核心：同一等级的电话线一起处理，避免重复计算，同时记录合并的分量信息用于回溯。

2. 双指针与 C 公司合并

// 初始化 C 公司并查集与哈希表
for (int i = 1; i <= n; i++) {
    fa[i] = i;
    mp[i][bel[i]]++; // bel[i] 是 K 公司最终的连通归属
}

// 枚举 K 公司等级（从高到低），双指针维护 C 公司
for (int i = alen, pos = 1; i >= 0; i--) {
    // 提升 C 公司等级，直到总对数满足条件
    while (pos <= B && X + anum[i] - Y < K) {
        int x = find(b[pos].x), y = find(b[pos].y);
        pos++;
        if (x == y) continue;
        // 累加 C 公司连通对数
        X += bbl[x].size() * bbl[y].size();
        if (bbl[x].size() > bbl[y].size()) swap(x, y);
        // 合并 C 分量，更新哈希表 mp 和共同对数 Y
        for (int j : bbl[x]) {
            mp[x][bel[j]]--;
            Y -= mp[x][bel[j]]; // 移除 x 分量中 bel[j] 的贡献
            Y += mp[y][bel[j]]; // 增加 y 分量中 bel[j] 的贡献
            mp[y][bel[j]]++;
            bbl[y].push_back(j);
        }
        fa[x] = y;
    }
    // 更新最小总价格
    if (X + anum[i] - Y >= K) {
        ans = min(ans, aval[i] + b[pos - 1].z);
        a1 = aval[i], a2 = b[pos - 1].z;
    } else break;
    // 回溯 K 公司分量，恢复到 i-1 等级
    reverse(asp[i].begin(), asp[i].end());
    for (int j : asp[i]) {
        for (int k : abl[j]) {
            mp[find(k)][bel[k]]--;
            Y -= mp[find(k)][bel[k]];
            bel[k] = j; // 恢复 k 在 K 公司的归属
            Y += mp[find(k)][bel[k]];
            mp[find(k)][bel[k]]++;
        }
    }
}

• 核心：双指针确保 C 公司等级仅提升不下降，降低时间复杂度；回溯 K 公司分量时，同步更新共同对数 (Y)，保证统计准确。

3. 关键变量说明

• (X)：C 公司单独的连通对数（(\sum \binom{s}{2})，(s) 为 C 分量大小）。
• (Y)：两家公司共同的连通对数（同一 C 分量且同一 K 分量的住户对）。
• (anum[i])：K 公司等级为 (aval[i]) 时的单独连通对数。
• 总连通对数：(anum[i] + X - Y)（容斥原理，减去重复计数的对数）。

时间复杂度与空间复杂度

• 时间复杂度：(O((A+B)\log(A+B) + N\alpha(N)))，其中 (\alpha) 为并查集的阿克曼函数反函数（近似常数）。排序复杂度为 (O(A\log A + B\log B))，并查集合并与回溯复杂度为 (O((A+B)\alpha(N)))，双指针遍历复杂度为 (O(B))。
• 空间复杂度：(O(N + A + B))，用于存储并查集、连通分量列表、哈希表等。

关键结论

1. 枚举 + 双指针：通过枚举 K 公司等级，用双指针维护 C 公司等级，避免暴力枚举所有可能的等级组合，将时间复杂度从 (O((A+B)^2)) 降至线性对数级别。
2. 容斥原理去重：通过哈希表统计共同连通对数 (Y)，利用容斥原理计算总对数，确保不重复计数。
3. 回溯与撤销：K 公司的回溯机制（记录合并信息并恢复）是实现高效枚举的关键，避免重复预处理。