题解：P7214 [JOISC 2020] 治療計画

· · 题解

题解区大家都是线段树做法，这里提供一个有点劣但很好理解的 KDT 做法。

先考虑简化版的问题：如果没有时间限制，把每个计划抽象成一条线段，我们要做的其实就是选代价最小的线段覆盖 [1, m] 的区间。

这个东西本质就是带权最小线段覆盖，我们考虑一个最短路做法。

考虑每条线段接下来的后一条线段可以是哪些，显然只要两条线段相交，我们就可以从前面的线段向后面的线段连边，连好所有边之后跑一遍点权最短路即可。但这样连出来的边数是 O(n^2) 的，考虑线段树优化建图，这样就确保连出的边数是 O(n \log n) 的。

现在有了时间限制，加一维时间轴，此时每个治疗计划都可以抽象成一个斜边的两个端点为 (l_i, t_i), (r_i, t_i) 的等腰直角三角形。此时我们仍然要覆盖 [1, m] 的区间，不过从选代价最小的线段变成了选代价最小的等腰直角三角形。

这个东西怎么做？其实和刚才差不多，仍然是每个等腰直角三角形向它能覆盖的等腰直角三角形连边，注意到 i 能向 j 连边当且仅当 |t_i - t_j| \le r_i - l_j + 1。

更形象地说，每个点连边的区间，应该在一个斜边与时间轴重合的等腰直角三角形中。

一个点向一个一维的线段连边，我们可以用线段树优化建图解决。而一个点向一个二维的区域连边，我们考虑用 KDT 或二维线段树优化建图。

但 KDT 只能解决四边与坐标轴平行的矩形的问题，目前我们的二维区域是一个斜边与时间轴重合的等腰直角三角形，所以我们考虑将坐标轴旋转 45\degree，然后再用 KDT 优化建图。

此时我们发现：这个问题完全被转化成了 P5471。事实上，我的本题代码也是完全照搬自我写的那道题的代码，稍加修改就能 AC。

不过一个需要注意的细节是：由于这个做法涉及到旋转坐标轴，旋转之后的坐标是个浮点数，会产生精度误差，所以需要设置一个允许存在误差的范围来避免在这个地方挂掉。而且不要设置的太小，我设置成 10^{-7} 时会在一些点上挂掉，设成 10^{-5} 才能 AC。

还有更多代码上的细节，无法一一赘述，因此提供一份参考代码。

code