题解：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}$ 了。

${\rm eq}$ 比较万能，不受限制影响。如果 ${\rm eq}$ 比较多其实是没什么影响的，但是如果数量不够可能就寄了。

我们设状态 $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_{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，实现的时候在梦游，空间写的是 $O(n^2)$。