题解 P6902 【[ICPC2014 WF]Surveillance】

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

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

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

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

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