题解：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)$。\ [提交记录](https://codeforces.com/contest/2143/submission/339987721)

文章操作