CF2162H 题解

后半部分不同于已有题解的做法。

固定 $x$，所有数只分为 $<x,=x,>x$，分别记为 $0,1,2$。那么每个区间全 $\leq 1$ 或者全 $\ge 1$，分别记为 $A,B$ 类区间。你发现这里确定好 $A,B$ 类区间的分配之后限制比较明确，考虑确定好所有区间的种类后，令 $i$ 有 $c_i$ 个，只被 $A$ 覆盖有 $a$ 个，只被 $B$ 覆盖有 $b$ 个，不被覆盖的位置有 $t$ 个，限制为 $c_0\leq t+a\wedge c_2\leq t+b\wedge c_0+c_2\leq a+b+t$，这样对 $a,b,a+b$ 的限制分别是定值，并且问题重点就迁移到 $(a,b)$ 的刻画上。将合法的 $(a,b)$ 放在平面上，合法的区域是右上部分一个单调区域。

考虑 dp，固定 $a$ 时最大化 $b$ 的个数，这个就与 $x$ 具体的值无关。转化为对位置钦定 $A,B$，这样要求不存在某个区间同时含有 $A,B$。直接对 $1\sim n$ 的位置的 $ABx$ 串做 dp，并记录当前 $A$ 的个数 $a$，值为 $f_{i,a,A/B}=\max b$。假设当前位置决策为 $A$，如果上一个钦定的位置是 $A$ 那么可以直接转移（前面的位置限制显然更严），否则上一个位置钦定的是 $B$，可行的转移位置是一段前缀。

使用前缀 $\max$ 优化对位置的枚举，时间复杂度 $\mathcal O(n^2+m)$，后者是需要求出覆盖每个点区间的最小 $l$，这个东西从右往左扫描线，记录 $i\leq r$ 的最小 $l$ 即可。

另一个 dp 过程中的思路：显然被包含的区间无用，可以去除。接下来认为 $l,r$ 分别严格单调递增，从 $i-1$ 转移到 $i$ 讨论交集即可。