526互联

杂题

发布时间 2024-01-01 11:26:20作者: aCssen

CF61E

\(f_{i,j}\) 表示以 \(i\) 为结尾，长度为 \(j\) 的严格下降子序列的数量。

则 \(f_{i,j}= \sum_{1 \le k < i,a_k>a_i}f_{k,j-1}\)。

用树状数组优化，所以要先离散化。

时间复杂度 \(\mathcal{O}(n \log n)\)。

优越性在于可以扩展到长度为 \(m\) 的子序列的情况。