Luogu分析一个显然的想法是我们每次选能选的最短的一根。但是这样会有一些问题，就是选了最短的之后两边的就不能选了，然后答案会偏大。这个其实比较好解决。假设当前最短的长度为 $l_u$，左右两边的长度分别为 $l_L$ 和 $l_R$，那么我们在选 $u$ 之后加一个长度为 $l_L+l_R-l_u$ 的候选项，表示删掉 $u$ 而选左右两个。这样子就是对的了。用堆维护以上过程，双向链表维...
BZOJ分析只考虑选的点都在线段下方的情况，在线段上方的情况可以通过将纵坐标取反一样的做。首先考虑线段的纵坐标无限大的情况，显然线段的左右边界会卡在相邻的两个颜色相同的点之间。那么只需要将所有点按横坐标排序，维护一下上一个某种颜色的点，再用树状数组维护区间内点的个数即可。现在把线段向下移动，假设现在纵坐标刚好比某个点 $u$ 的纵坐标小 $1$，此时线段左右边界会卡在上一个和 $u$ 颜色相...
Luogu分析考虑到如果两个点之间没有边，那么这两个点一定会分在一个集合里。也就是说我们要求的实际上是补图的连通块。但是直接连边去求边数是 $n^2-m$ 级别的，显然存不下。考虑一个很暴力的想法：每次找一个还没有找连通块的点，然后 BFS 找连通块。具体就是扩展 $u$ 时，先标记 $u$ 的所有出点，然后所有没有找到连通块的没有被标记的点都和 $u$ 在一个连通块中。问题就是怎么维护还没...