P2513 [HAOI2009] 逆序对数列 分析 & 排列 DP & 前缀优化

__ryp__ · 2024-02-09 13:04:55 · 个人记录

排列 DP 的一般状态是：f(i, j) 代表 1 到 i 的排列中，目标组合已经有了 j 个。

那么套用到本题就是：f(i, j) 代表 1 到 i 的排列中，已经有了 j 个逆序对。

我们很容易注意到，由于 i 在 1 到 i - 1 的排列中是最大的，我们无论将 i 插入到哪里都会让整个序列的逆序对数量加上这个位置后面的数字数。

形式化地，设 i 被插入到 p 的位置，其中 p\in [0,i - 1]，那么，逆序对将会比原来多 i - p - 1 个。也即，f(i, j) = \sum\limits_{p=0}^{i-1}f(i-1, j - i + p + 1)。规约一下，得到

这个转移就是 O(n) 的，于是整体 O(n^2k)，显然不行。

我们考虑：等号右边是一个求和，而且求和区间随着 j 的移动而单增。那么，我们可以维护一个前缀和。

我们维护 \sigma(j) = \sum\limits_{k=0,j-i+1}^j f(i-1,k)，那么在转移的时候，有 f(i,j) \gets \sigma(j)，随后 \sigma(j) 更新上 f(i, j) 的值。

此时如果 j - i + 1 移动，我们就需要减去移动的这一段空窗，即 f(i - 1, j - i + 1)。

典型的黄题比绿题难……