题解：CF2162H Beautiful Problem

· · 题解

一个自认为简单不少的做法。

以下分别记 {\rm low,eq,high} 为 <x,=x,>x 的数。

首先，f(a,x,l,r) 的限制等价为「a_l,a_{l+1},\dotsc,a_r 中不能有 {\rm low} 或 {\rm high} 其一」。

记 L_k 表示覆盖 i 的区间中，左端点离 i 最远有多远，形式化地，L_k=i-\min_{i\in[l,r]} l。如果 i 不被任何区间覆盖，设 L_i=0。R_i 类似定义为右端点最远的距离。则如果将 a_i 填入 {\rm low}，那么 [i-L_i,i+R_i] 中都不能有 {\rm high} 了。

我们设状态 $f_{i,j}$ 表示现在已经填完 $a_1,a_2,\dotsc,a_i$ 且 $a_i$ 填的是 ${\rm low}$，总共填了 $j$ 个 ${\rm low}$ 时最少需要多少个 ${\rm eq}$ 才不会爆。 经典地，容易说明若 $i<j$，则 $i-L_i\leq j-L_j$ 且 $i+R_i\leq j+R_j$。这说明，一个 ${\rm low}$ 带来的限制不会跨过另一个 ${\rm low}$ 去管辖远方的位置。 所以我们可以暴力转移，直接枚举上一个 ${\rm low}$ 填在哪了，设为 $k$。中间必须填 ${\rm eq}$ 的位置共有 $\min(i-k-1,R_k+L_i)$ 个，其它的都可以填入 ${\rm high}$。 故，转移方程如下： $$ f_{i,j}\operatornamewithlimits{\longleftarrow}_{k<i} f_{k,j-1}+\min(R_k+L_i,i-k-1) $$ 初始 $f_{0,0}=1$。 再记 $g_{j}$ 表示 ${\rm low}$ 有 $j$ 个时 ${\rm eq}$ 最少需要多少个。可以 $g_j\gets f_{i,j}+R_i$ 得到。判断一个 $x$ 是否合法时，直接算出 ${\rm low}$ 和 ${\rm eq}$ 的数量查表即可。 现在 $f$ 的计算是 $O(n^3)$，可以使用手法优化一下。我们分讨转移时取到了 $\min$ 中的哪一项。对于一个确定的 $i$，存在一个分界点，使得分界点之前的 $k$ 取到第一项，分界点后取到第二项，且分界点本身关于 $i$ 也是单增的。取到第二项的可以单调队列维护，第一项直接维护不在单调队列里的最优决策点即可。 直接实现复杂度 $O(n^2+m\log m)$。如果喜欢赤石可以卡到时间 $O(nm)$，空间 $O(n+m)$。 [Submission](https://codeforces.com/contest/2162/submission/349842059)，实现的时候在梦游，空间写的是 $O(n^2)$。