自动搬运

查看原文

来自洛谷，原作者为

	鏡音リン 希望大家都能成为自己想要的样子呐

搬运于2025-08-24 22:25:04，当前版本为作者最后更新于2021-01-28 18:27:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意：一个环上有 $n$ 个点，给定了 $k$ 个环上区间，求在这些区间中最少选择多少个可以覆盖环上所有的点，或判断无解。只输出最小值。

考虑一个弱化版的问题：把环改为链，应该怎么做。可以使用贪心算法：假如当前选择的区间已经覆盖了前 $x$ 个点，为了覆盖第 $x+1$ 个点，一定要再选择一个左端点小于等于 $x+1$ 的区间。那么我们加入一个左端点小于等于 $x+1$，且右端点位置最大的区间，这样能尽可能覆盖最多的点，一定是最优的。此时把 $x$ 更新为这个右端点的位置。初始时令 $x\leftarrow 0$，不断重复这个过程选择加入的区间，直到 $x=n$ 时终止循环。若某一次选择区间后 $x$ 仍不变，说明第 $x+1$ 个点不可能被覆盖，无解。对每个 $1\le i\le n$ 预处理出左端点小于等于 $i$ 的所有区间中最大的右端点位置，就可以用 $O(n+k)$ 的时间预处理，$O(n)$ 选择区间，总时间复杂度 $O(n+k)$ 解决这个问题。

扩展一下上面的问题：仍然是链，有多次询问，每次给定一个区间 $[l,r]$，询问覆盖区间中所有点的答案。上面的算法可以很自然地扩展到询问一个区间的情况：把 $x$ 的初始值改为 $l-1$，终止条件改为 $x\ge r$ 即可。为了优化多次询问的时间复杂度，可以使用倍增：用 $f(x,y)$ 表示已经覆盖了前 $x$ 个点，按照上述方法再选择 $2^y$ 个区间，能够覆盖前多少个点。对所有 $0\le x< n,~0\le y\le \lfloor\log_2(n) \rfloor$ 预处理出 $f(x,y)$。然后倍增二分，从 $\lfloor\log_2(n) \rfloor$ 到 $0$ 枚举 $y$，如果当前 $f(x,y)<r$ 就选择这 $2^y$ 个区间，并令 $x\leftarrow f(x,y)$。最后若 $x<r$ 则再选择一个区间，过程中判断无解的情况。时间复杂度可以做到 $O(k+n\log n)$ 预处理，$O(\log n)$ 处理单次询问。

回到环上的问题来。在任意两个相邻点之间破环成链，不妨选择方便实现的点 $1$ 和点 $n$ 之间。对于所有经过这一分割点的区间，设这个区间是 $[l,n]\cup [1,r]$，把它们记录下来，然后添加 $[l,n]$ 和 $[1,r]$ 两个区间。添加这两个区间并不会使答案发生变化。添加之后，一定有一组最优解包含至多一个经过分割点的区间。证明如下：如果一组最优解包含两个经过分割点的区间 $[l_A,n]\cup [1,r_A]$ 和 $[l_B,n]\cup [1,r_B]$，把这两个区间改为后添加的 $[\min(r_A,r_B),n]$ 和 $[1,\max(l_A,l_B)]$ 两个区间，仍然能覆盖所有的点，这仍然是一组最优解。如果还有超过一个经过分割点的区间，就继续这样做，最终一定能得到一组包含至多一个经过分割点的区间的最优解。

那么，我们可以枚举选择的经过分割点的区间是哪个，若为 $[l,n]\cup [1,r]$，用上面的算法求出链上覆盖 $[r+1,l-1]$ 中的点需要选择多少区间，并更新最小值。注意也可以不选择经过分割点的区间。总体时间复杂度 $O((n+k)\log n)$。