Link
对 MST 的理解加深了！
暴力建边跑 MST 无法接受，边的数量级太高。怎么优化这个过程？考虑 Kruskal 构建的过程，每次只联通两个独立的连通块。这道题同理，将 \(a, b\) 升序排序，注意到每一行、每一列的所有边权都是相等且连续的，考虑将每个单独的行、列视为整体来处理。对于没有横竖相交的情况，我们肯定是直到有交之前一直连边使得整条线（行或者列）相连通，代价 \(n - 1/m - 1\)，如果遇到了交叉点，此时的交叉点视为已经并入连通块，只需要将没有连入图的点接上去即可，第一条相交的线肯定是产生全部贡献的，维护 \(r, c\) 表示已经加入的行和列，分类讨论不难得到结论，如果 \(r, c\) 都为 \(0\)，直接加入当前维护的数列所有段，否则要减去已经在连入的点数。
按照 Kruskal 的算法跑所需的边数在这个题难以计算，怎么办？直接跑完所有边即可，量级也只是 \(n + m\) 的，因为后面的不优秀的边必定不会被选入。复杂度是 \(O((n + m) \log (n + m))\) 的。
#include <bits/stdc++.h>using i64 = long long;constexpr int N = 3e5 + 7;int n, m, r, c;
i64 ans = 0;std::vector<std::pair<int, int>> a;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cin >> n >> m;for (int i = 1, x; i <= n; i++) {std::cin >> x;a.push_back({x, 0});}for (int i = 1, x; i <= m; i++) {std::cin >> x;a.push_back({x, 1});}std::sort(a.begin(), a.end());for (const auto &[v, k] : a) {if (k == 0) {if (r && c)ans += (i64) (m - c) * v;elseans += (i64) (m - 1) * v;r++;} else {if (r && c)ans += (i64) (n - r) * v;elseans += (i64) (n - 1) * v;c++;}}std::cout << ans << "\n";return 0;
}