题解 CF1633E

Legitimity · 2022-02-02 22:39:27 · 题解

考虑 kruskal 的过程，实际上 MST 的构成只和按边权排序后结果有关。考虑任意两条边 i 和 j 之间的大小关系以 x=\dfrac{w_i+w_j}{2} 为界，只有 O(m^2) 种 MST ，我们可以对于每种情况跑出对应的 MST，此部分的时间复杂度为 O(m^3\log m)。（常数很小，且有 cf 的神机加持，跑的很快）

对于同种 MST，处理出要选那些边后，对于不同的 x 可以用双指针处理。（具体来说按升序处理 x，同时按升序加入满足 w_i\leq x 且在 MST 中的边，维护它们的数量和权和）

综合一下，我们得到这样一个算法：将询问的 x 按升序排序，同时按升序处理不同段的 MST，求出当前段的 MST ，钦定选哪些边，后按升序处理询问，处理询问时按升序加边。（三指针）

如果使用快排，时间复杂度为 O(m^3\log m +q\log q)。

你问给长度 10^7 的数组排序不会有问题吗？当时我也觉得跑不过去，但事实证明你可以永远相信 std::sort 的常数，如果实在担心就用松氏基排。（雾）