CF1620F Bipartite Array 题解

注意到若存在三元组 $(i,j,k)$ 满足 $i<j<k$ 且 $a_i>a_j>a_k$，则此时 $i,j,k$ 三个点在无向图上构成一个三元环，此时无向图一定不是二分图。若不存在任何一组这样的 $(i,j,k)$ 则此时图上不存在环，一定是二分图。

因此数组 $a$ 是二分的 的充要条件 即为序列的最长下降子序列长度不超过 $2$。此时直接 dp 可以做到 $O(n^3)$ 时间复杂度解决问题。

考虑使用 Dilworth 定理，若一个序列的最长下降子序列长度为 $d$，则其最少可以被划分为 $d$ 个不下降子序列（若数组元素互不相同则可以被划分为 $d$ 个上升子序列）。因此序列的最长下降子序列长度不超过 $2$ 一条件可以被转化为 $a$ 可以被划分为两个上升子序列。

此时可以设 $f_{k,i,j,0/1,0/1}$ 表示当前处理了前 $k$ 个元素，其中第一个上升子序列最后一个元素位置是 $i$，第二个上升子序列最后一个元素位置是 $j$，$a_i$ 没有取反 / 取反，$a_j$ 没有取反 / 取反是否存在这样的序列。看上去时间复杂度仍然为 $O(n^3)$。此时考虑用染色的 trick，有 $\max(i,j)=k$，因此此时只处理 $i,j$ 两个维度可以做到 $O(n^2)$。然后套路的判定性问题把一维信息压到答案里变成最优化问题可以做到 $O(n)$ 解决。