你学了一坤年OI甚至还不如个锤子。

· · 个人记录

你花了九牛二虎之力算出 C 的值之后，小 I 却告诉你他已经找开锁师傅用锤子暴力破解了。在你的百般劝说下，小 I 承诺以后锁车不用有大于等于一万个拨圈的密码锁。

题目：P9120（NOI春测2023 T4）

好题，可惜脑子抽了，一眼没秒。

$k=2$，发现全局最大值和全局最小值放在同一列肯定不优，先把这俩错开，然后...... “有 $n$ 个位置，每个位置上两个数二选一，最小化极差。” 出门左转卡牌游戏，请。啊不对看错题了： “有两行每行 $n$ 个位置，每个位置上两行之间的数可以交换，最小化两行中极差最大值。” 这不卡牌游戏的翻版吗？一行前缀指针一行后缀指针，按卡牌游戏那样配合布尔数组双指针翻牌求解就OK了。 $k=3,4$：上面的做法有点难搞了，发现是最大值最小，二分转check。 用一样的思路钦定最大最小值位置，发现：未被确定的一行的某个数如果确定了，这一列的数也就都确定了。因此对于拨圈位置可以转化成在某一行上选点，前面两行造成的限制可以转化为某些点不能选。注意我们选点还有一个性质：$n$ 个位置的点转化成 $n$ 种颜色，选点必须包含全部的 $n$ 种颜色，对应 $n$ 个位置都选了数。 $k=3$ 时，相当于在值域数轴上选点，使得存在长度为 $c$ 的线段包含所有颜色的点。这个好办，硬扫就行了。 $k=4$ 时，数轴变成了二维平面，线段也成了边长为 $c$ 的正方形。扫描线维护某一维的一个区间来转成一维，另一维变成了需要支持删点加点动态查询的 $k=3$ 时的问题。 注意：考虑数轴扫描时，当一个点存在，设其对应值为 $x$ ，它会在 $[x,x+c]$ 的这一段区间中被扫到（也可能是另外半边，和扫描线端点设置以及扫描方向有关），在数轴上是一条线段。对于同种颜色的点，由于其个数很少（$\le k$），因此在数个相同颜色的点的贡献区间重叠时可以暴力合并成同一条线段，新端点为外侧的端点。这样构成的相同颜色的线段不会有重叠，说明的是这一段这个颜色能被包含到。 因此，利用以上优秀性质，用线段树维护每个位置被多少线段覆盖（这些线段必定不同色，原因见上面构造时带来的性质），这个用区间加维护，同时维护区间 $\max$，当最大值等于 $n$ 时说明存在一段能被长度为 $c$ 的线段覆盖的子线段包含 $n$ 种颜色的不同点。点集变化时暴力重构线段即可，单次操作复杂度是 $O(k\log a)$ 的。 总时间复杂度最坏大概 $O(T(nk \log (nk)+k^4nk\log^2 a ))$，貌似可以过题。 实现有时间回头再补，最近被理综恶心飞了。