P12196 [NOISG 2025 Prelim] Lasers 2 题解

· · 题解

我们假设，操作结束后，位置 [x_1,y_1],[x_2,y_2],\cdots,[x_n,y_n] 的激光可能会被挡住，其他位置的激光一定不会被挡住，那么所有满足 \exist j \in [1,n],x_j \le l_i \le r_i \le y_j 的滑动墙 i 都不需要解锁，而其余的滑动墙都必须解锁，否则一定会挡住其他激光；同时，设 m=\max\limits_{i=1}^h r_i-l_i+1，则需要满足 \exist z \in [1,n],y_z-x_z+1 \ge m，否则最长的滑动墙没有地方放置。我们不需要担心解锁后的滑动墙再挡住其他激光，因为我们可以把这些滑动墙都放到最长的滑动墙后面。

于是我们考虑一个 dp：设 f_{i,j,0/1} 表示考虑到第 i 列，目前有 j 列激光没有被挡住，且当前不存在 / 存在 y_z-x_z+1 \ge m 的正整数 z 的，不需要解锁的滑动墙的最大价值和。初始时 f_{0,0,0}=0，其余均为 -\infty。

有一个朴素的转移方式是：

但是直接这样做是 \mathcal O(w^3) 的，考虑优化。

注意到，影响时间复杂度的第二种转移中 j 的值不变，于是我们可以更改一下枚举顺序，先枚举 j 再枚举 i，并把所求的信息拍到线段树上维护。

具体而言，对于每个 j，我们开两棵线段树 T_0,T_1，在 T_s 的第 x 个叶子处维护 f_{x-1,j,s}+\sum_{x \le l_k \le r_k \le i} c_k 的值。每次 i 增加 1 后，我们找到所有 r_k=i 的滑动墙，并给 T_0 和 T_1 的前 l_k 个叶子所维护的值增加 c_k，因为这些叶子满足 x \le l_k \le r_k \le i；同时，我们把 f_{i,j,0} 的值赋为 T_0 的第 [i-m+2,i] 个叶子的权值的 \max，把 f_{i,j,1} 的值赋为 T_0 的前 i-m+1 个叶子与 T_1 的前 i 个叶子的权值的 \max，并更新 T_0 和 T_1 的第 i+1 个叶子的权值。这样我们就完成了第二种转移，第一种转移直接暴力做即可。

于是我们就快速求出了 f 数组，那我们找到最大的满足 \sum c_i-f_{w,a,1}\le k 的正整数 a 即为答案。时间复杂度 \mathcal O(w^2 \log w)。