固定 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 讨论交集即可。