题解 P9120 [春季测试 2023] 密码锁

· · 题解

分四种情况考虑：

输出最大值减最小值。

注意到答案的上界为最大值减最小值，要想低于这个上界就必须让最大值与最小值不在同一行。

不妨令最大值 mx 在第一行，最小值 mn 在第二行，二分极差最大值 mid。对于第一行，判定条件为 mx-a_i\le mid，第二行则是 a_i-mn\le mid。

时间复杂度 O(n\log n)。

现在除了最大值和最小值所在的行外又多出了一行。首先固定最大值在第一行，通过转锁的方式调整最小值所在的行号，对每个行号依次处理。

同样二分极差最大值 mid。除最大最小值外的锁通过转锁能得到这一行的所有可选值。对于这些可选值，我们希望找到一个长度 \le mid 的区间使得每一把锁都有至少一个可选值在区间内。

先将所有可选值排序，再通过双指针滑动窗口的方式依次枚举区间。设 cnt_i 为每一把锁可选值在区间中的出现次数，那么判定条件即为 \sum_{i=1}^n[cnt_i>0]=n。每次移动指针时 cnt 的变化量是 O(1) 的，很好维护。

时间复杂度 O(n\log^2n)。

还是一样二分 mid，不过这种情况可选值变成了一个二维点对 (x,y)。

我们放在二维平面上来考虑。设一种合法构造中第一维的最大值为 x_0，第二维最大值为 y_0，那么点 (x_0,y_0) 就可以表示一种方案。

对于一个点 (a,b)，最大值点对应该在 x_0\in[a,a+mid],y_0\in[b,b+mid] 的正方形中。一把锁构成的合法点集就是这些正方形的并。

考虑使用扫描线转化为数轴问题，合法点集在扫描线上的投影就变成了若干个区间的并。注意正方形，也就是扫描线中的区间个数对于每一把锁是 O(1) 的，可以对每一把锁建立一棵珂朵莉树来维护区间并。

具体而言，珂朵莉树维护的东西形如 (l,r,x)，表示区间 [l,r] 被覆盖了 x 次。每次增删区间时，暴力修改这些三元组即可。

最后用一棵线段树维护当前每个位置被多少的合法点集包含。这棵线段树需要支持区间加减和区间查询最大值。如果存在位置被所有锁的合法点集包含，那么就有解。

时间复杂度 O(n\log^2n)。

  1. 多测清空：注意我们开的是值域线段树，不能直接暴力清空，需要打一个清空标记。同样的，扫描线也是基于值域的，需要记录哪些位置有操作。
  2. 关于最大最小值：需要特判它们在同一把锁，或者最大值等于最小值（也就是所有数均相同）的情况。
  3. 关于转锁：注意二分时不要去转最大最小值所在的锁。

Code （10KB，慎点）