POI2011 收缩点

题目:

  给定 个点 ,将其分成不多于 个连续的段:

  

  其中 ,且对于 ,子序列 用一个新点 替代。这时我们说 这些点被「收缩」到了点 ,从而产生一个新的点集 。两个点集的相似度定义为 这些点与其对应的「收缩」后的点距离的最大值:

  

  其中 表示 之间的距离,公式为:

  

  给定 个点组成的序列,你需要将其「收缩」为最多 个点,使得相似度最小。原序列可以任意切割。受限于浮点数的精度限制,只要答案比最优解多出不超过 即算正确。

思路:

  要求最大值最小,很直接的思路就是二分最大值。假设现在有一个数据结构能够维护一个点集,支持插入一个点和查询这个点集的最小圆覆盖。在二分出最大值之后,只要把元素一个一个往里插就能计算出至少要分成多少组了。
  可惜没有这样的数据结构........
  而期望复杂度求最小圆覆盖的算法要求数据随机,所以每次只能在 的复杂度内算出 之间所有点组成的最小圆覆盖 。一开始的想法是再做一次二分,通过二分右端点来找到当前左端点对应的右端点。但是这样的做法是有问题的,因为这样无法保证检验过的区间与跳过的区间长度有关,最坏情况下复杂度就会达到 了。
  既然不能二分,那就试着倍增。设当前左端点对应的区间长度为 ,先通过检测 来找到 的最高二进制位,再从高位到低位在满足限制的情况继续延伸(类似倍增求 lca),这样就能保证检验过的区间和跳过的区间同阶了。检验一次二分值的复杂度应该就是 的了。