题解：CF1583H Omkar and Tours

snowfallen · 2026-04-24 21:10:25 · 题解

记录一个自己想到的思路。

我们先将询问按 v 排序，将边按 c 排序，通过并查集维护连通块的最大值求出第一问的答案。

然后发现第二问可以二分，于是考虑整体二分。

然后又发现整体二分之后，每一个询问的一个判定问题 v 和 m 就是边的 c_i\ge v 且 t_i>m，这是一个二维偏序问题，可以通过 CDQ 分治解决，在 CDQ 里套用并查集维护连通块的最大值的方法。

整体二分可以一层一层的通过循环实现，这样 CDQ 分治起来更方便。

时间复杂度 O(n\log n\log V)，离散化后变为 O(n\log^2 n)。