题解：CF2143D2 Inversion Graph Coloring (Hard Version)

· · 题解

子序列 b 不合法当且仅当 \exist i<j<k,b_i>b_j>b_k，也就是说 b 的 LDS 不超过 2。那么根据狄尔沃斯定理，条件等价于 b 能被不超过两个上升子序列覆盖（最长反链等于最小链覆盖）。\ 设状态 f_{i,j,k} 表示前 i 个数组成的两个上升子序列中一个结尾值是 j，另一个是 k 的方案数。为了不算重，我们钦定 j\geq k，并且尽量在 j 处转移。\ 写出在 i 处的转移方程：

f_{i,a_i,k} \gets f_{i-1,j,k} & k\leq j\leq a_i \\ f_{i,j,a_i} \gets f_{i-1,j,k} & k\leq a_i< j \end{cases}

对于第一种转移，直接对每个 k 开一个树状数组，转移相当于单点修改前缀查询；第二种转移对每个 j 开一个树状数组，转移类似。总时间复杂度 O(n^2\log n)。\ 提交记录