我去这么巧妙，咋想到的？？？ 看似总共有 2n2^n2n 种选择方法，十分困难。 定义相邻两个点之间的为一条线段。 注意到对于每条线段，每组端点两种方法中，有且仅有一种会覆盖到它。 又注意到显然存在一种覆盖方法，使得至少一条线段不被覆盖。 然后我们发现根据第一个结论，枚举不被覆盖的线段，每组点对的选择方法可以唯一确定。 所以此时选择方法只有 O(n)O(n)O(n) 种。 然后套个线段树 O(nlog⁡n)O(n\log n)O(nlogn) 就做完了。 大受震撼。