题解：P14382 [JOISC 2017] 开荒者 / Cultivation

· · 题解

需要脑电波的不简单题。

首先有一个观察是如果我们分别确定了所有方向刮的风的数量 u,d,l,r ，那么覆盖的地方应当是若干宽为 u+d ，长为 l+r 的矩形，于是可以枚举四个方向做到 O(R^4n) 。

然后考虑只枚举 u 和 d 会发生什么，显然现在的草在平面上会扩展为若干长条状物。

对于每一行来讲，我们记 a_i 为该行第 i 个有草的格子的列号，该行共有 k 个点。那么这一行对 l,r 的限制只有 l\ge a_1 -1,r\ge C-a_k,l+r\ge a_{i+1}-a_i-1。

发现 a 不同的行只有 O(n) 个，所以可以做到 O(R^2n^2)。

同时我们注意到每一行的点扩展前在纵坐标上一定是一个区间，也就是说我们可以把初始的点按照纵坐标排序后，对每个区间求出对应的 a_1-1,C-a_k,\max(a_{i+1}-a_i-1)，这样可以把时间优化到 O(n^3+R^2n)。

接下来就要优化枚举 u,d 的部分，如果固定 u+d ，那么 u,d 本身的改变等价于将整个平面上下移动。所以我们可以枚举 u+d 之后，对整个平面做长度为 R 的滑动窗口，并维护三个值的单调队列。

窗口能够滑到的地方只有 O(n) 个，也即每个条状物的最上段，因此时间复杂度为 O(n^3+nR)。

感受一下有用的 u+d 的数量不会太多，我们称会对 a 集合有实质性改变的 u+d 为有用的。

此时的 u+d 只会有两种情况，第一种是在某个条状物为顶时恰好卡到边界，第二种是将某个条状物延伸到恰好与另一个条状物相接。用数学语言描述就是 x_i+R-1=x_j+u+d ，x_i+u+d=x_j-1。

也就是只有 O(n^2) 种，时间复杂度 O(n^3)。

总结一下，这个题的思维链比较长但是没有什么跳跃，需要不断找出结论和一些关键的观察，还是非常依赖熟练度和对结论的感知能力的。

上面的只是一种可能的思路，官方题解给出的就是一个不太一样的思考路径。