P11099 [ROI 2022 Day 1] 照明 题解

· · 题解

允许方向 1：

每个点方向确定，一遍排序维护倒阶梯即可，复杂度 O(n\log n)。

允许方向 1,2：

考虑所有 y 坐标相等的一个点对 (x_1,y),(x_2,y)，一定可以让 x 较小的那个向 1，让 x 较大的那个向 2，这是不冲突且全局最优的。处理完之后所有点 y 坐标唯一，且原矩形被截取了一段上边界。按照 y 坐标从小到大排序。

我们按照顺序考虑这些点的决策，维护当前空白矩形的四边界，设当前考虑第 i 个点：

容易发现每次最多只会分支出唯一一个决策情况，这部分复杂度 O(n)，瓶颈在排序，复杂度为 O(n\log n)。

允许方向 1,3，n\le 5000：

考察一种最优子结构：若有两点 (x_i,y_i),(x_j,y_j) 满足 x_i\le x_j,y_i\le y_j，此时让 i 向 1，j 向 3 一定最优，因为这样达到了 i,j 向任意 1,3 覆盖的并。

考虑暴力一点的做法，n^2 枚举所有点对判定是否构成最优子结构。对于任意一个最优子结构，它会剩下一个左上角矩形和右下角矩形。如果我们想象所有最优覆盖过的图象，会发现所有剩下的空白矩形会分布在左上到右下的这段线上，且一定有所有矩形边界在一维上不相交。

剩下没有决策的点，一定在剩下的若干个空白矩形里面，且 x_i<x_j,y_i>y_j。我们注意到，不同空白矩形内的点互不影响，因此可以转化为若干个子问题。现在假装我们通过一些手段找到了若干个矩形，以及提取出了矩形内的点，只需要计算每个矩形内的最优解相加即可。

现在我们多了一个不存在顺序对的条件，这样就可以 dp 了，设 f_{i,j} 为 j 向 3 覆盖，[j+1,i] 向 1 覆盖的最优解，g_{i,j} 表示的意义恰相反。转移考虑新开一个新的方向或者延续，状态是 O(n^2) 的，转移 O(1)，具体地，记当前矩形边界左上角为 A_0,A_1，右下角为 A_2,A_3，则有：

f_{i,j}+(A_2-x_{i+1})(y_i-y_{i+1})\rightarrow f_{i+1,j} g_{i,j}+(x_{i+1}-x_i)(y_{i+1}-A_3)\rightarrow g_{i+1,j} f_{i,j}+(x_{i+1}-x_{j})(y_i-A_3)\rightarrow g_{i+1,i} g_{i,j}+(A_2-x_{i+1})(y_j-y_{i+1})\rightarrow f_{i+1,i}

总复杂度 O(\sum n_i^2)=O(n^2)。

允许方向 1,3，n\le 100000：

上面那个做法不够优秀，我们考虑更给力一点的做法。

显然，如果一个点 1,3 方向都有点，那这个点是很废的，我们直接给他扬了。对于找最优子结构，直接上二维数点即可。

问题是如何找出最终若干个空白矩形和对应点。先考虑嗯做的方法，只需要拉出 O(n) 个所说的最优子结构，暴力两次横竖扫描线做矩形面积并，对于所有可能的边界判定并两次线段树上二分找极长空白段是可行的，大概需要两次矩形面积并和四轮线段树上二分，最后特判掉退化的矩形就能找出所有的空白矩形了。

但还是可以更优美一点，具体的，我们分两个序列维护仅右上有点的，和仅左下有点的，则每个点会对应到一个另一个序列上的连续段，做四遍双指针就能直接求出所有空白矩形四边界的坐标，直接排序对位就找到了所有空白矩形。这个做法更加优美但是细节极多。

预处理复杂度 O(n\log n)。

由空白矩形的性质，所有空白矩形会不交不重不漏连续地找到对应可能合法点列的点。继续双指针就可以进入子问题解决。

考虑优化上面那个 O(n^2)-O(1) 的 dp。发现这个东西和 \text{CSP-S 2024 T3} 形式很像，我们引入预支贡献的 trick，我们记 aa_i 为 [i,m] 都向 1 覆盖的权值和，bb_i 为 [i,m] 都向 3 覆盖的权值和，注意这里我们不考虑 i 与之前的权值，况且我们也不知道。

优化状态，我们只关注分段点，设 f_i 为 [i,m] 向 1，且 i-1 向 3 的最优解，g_i 恰相反，则转移可以改写为：

f_j+(y_i-A_3)(x_i-x_{j-1})-aa_{i-1}+bb_i\rightarrow g_i g_j+(A_2-x_i)(y_{j-1}-y_i)-bb_{i-1}+aa_i\rightarrow f_i

展开，合并无关项与相关项，则可以转化为 kx+b 的形式，因为查询坐标点差不单调，维护两棵李超线段树即可。有不少细节。

总复杂度 O(n\log n)。

允许方向 1,2,3：

更多的性质，更多的观察。

我们更准确地定义一下最优子结构：我们生成一个点集 S 是最优子结构，当且仅当，存在一个固定方法，使得 S 形成覆盖的区域恰等于 S 中所有点向所有允许方向覆盖的区域的并。容易发现这样是一定最优的。

那在允许方向为 1,2,3 的情况下，是否能找到类似子结构呢，当然是可以的。具体地，我们考察任一个长度为 3 的上升三元组点 (x_1,y_1),(x_2,y_2),(x_3,y_3)，满足 x_1\le x_2\le x_3,y_1\le y_2\le y_3，那么显然可以让 (x_1,y_1) 向 1，(x_2,y_2) 向 2，(x_3,y_3) 向 3，此时一定能取到最优方案构成最优子结构，即仅会剩下左上坐标为 (x_3,y_1) 的矩形，取到上界。

现在我们 O(n^2) 找到了每个点作为 (x_2,y_2) 时的最优子结构，直接扬了，最后会剩下一个右下矩形。记这个右下矩形左上坐标为 (mxx,mnn)。注意在找到右下矩形之后，要对于已经被最优情况覆盖过的点处理方向，显然在 (mxx,mnn) 左上的点不可能有影响，左下的必须向 1，右上的必须向 3。在给这些点定向之后，会继续缩小右下矩形，对于可能被新加入的点要继续定向。因为矩形最多被更新 O(n) 次，所以这部分复杂度 O(n^2)。

处理完之后，由 Dilworth 定理逆定理，因为不存在长度 \ge 3 的上升点列，因此所有点可以被划分进 \le 2 个下降点列。

考虑有哪些可能的点集向 2 覆盖可能最优，显然考虑固定住一个下降点列中的一个点，我们钦定它必须向 2，那么这个下降点列中任意一个点向 2 都不会优；对于另一个下降点列，显然也至多只会有在这个点右上角中的点中选一个向 2 覆盖。那可能最优的 2 方向覆盖仅有 O(n^2) 个。也就是说，当前可能最优的向 2 的点最多只会选择 2 个点。如果我们暴力枚举，0/1/2 个点向 2，就可以拼上只选 1,3 的做法了。这样至少是 O(n^3\log n) 的。

我们的结构还不够简洁，寻找另一种最优子结构，对于一个点，如果它右上角有至少三个点（下降三元点对），那也是可以取到下界的：只需要该点向 1，右上中间点向 2，剩下点向 3 即可达到最优。左下角三个点情况同理。

与上面类似地，找完所有这样的最优子结构，继续截取右下矩形，继续给被新覆盖的点定向，复杂度仍为 O(n^2)。

那么，这些最优子结构是否会冲突呢，显然是不会的，否则可以调整，这个画画就全出来了。

那么，现在我们有了另一个性质：对于任意一个点，其 1,3 方向都至多只有 2 个点。归纳一下上面向 2 覆盖的结论，发现就是所有互为左上右下即 1,3 方向的点对，那现在这样的点对数量瞬间仅有 O(n) 个了，如果我们套上之前的做法，那就可以 O(n^2\log n) 了吗？

有一些很严重的问题，那就是我们确定 2 之后，决策的矩形四边界不是完整的，左上角会缺一个，或者两个角，不能直接上李超树了。

但是问题不是很大，先考虑缺一个角的情况，在残缺的情况下处理 aa_i,bb_i，分 1,3 向覆盖是否会跨过残缺的角，分讨一下。若点在缺角内，就把边长当做去缺角外去做；若点在缺角外，如果该方向不会跨过缺角，那显然不影响就直接做，否则考虑对应点是否在缺角内，对应斜率查询的 x 也就有两种情况，讨论一下即可。然后我们就扩展了上面的做法，需要四棵李超树。

残缺两个角的情况看起来很复杂，因为可能有很多种情况，但是因为我们已经保证了两条性质，所以情况也只有 3 种左右，继续分讨，理论上维护六棵李超树即可。

允许方向 1,2,3,4：

反而这个是简单的，手玩一下可以发现，对于点数 \ge 4 的情况，一定可以覆盖全集，剩下的暴力搜索计算即可，复杂度 O(n) 或 O(4^n)。

我最后实现的允许方向 1,2,3 的包，先写了缺一个角情况的 n^2\log，然后发现就已经被卡常了。没有办法常数确实大，于是发扬人类智慧只取排序后的 100 个点跑就行。最后也是无奈写了这样一个有正确性缺陷和理论复杂度有一个部分不太对的代码，因为写了 26k 真的写不动了，但是思路和理论是没有问题的。如果读者要对拍的话建议不要用 loj 上的某份代码，因为他写的有问题在大规模小数据下错飞了，笔者用那份代码对拍对着错误的答案调了一万年。

最后，据说允许方向是 1,2,3 的包可以做到 O(n\log n)，我猜是继续找性质规约，或者动态调整地去做这个 dp，如果有会的人请联系我。