自动搬运

查看原文

来自洛谷，原作者为

	Starrykiller 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 22:29:33，当前版本为作者最后更新于2024-07-22 19:05:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

找出性质 DP。好题！

结论：最终序列 $a$ 由若干个连续等差下降子段构成，其中公差为 $-1$。（对于上升的情况，我们可以认为是若干个长度为 $1$ 的下降子段）

考虑证明：首先 $a$ 是一个排列。注意到 $a_i+2\gt a_{i-1} \iff a_i\ge a_{i-1}-1$ 即可。

套路地，考虑设计一个 dp。设 $f(i)$ 为值域 $[1,i]$ 已经分成若干个连续下降子段（可以认为是放在结果序列 $a$ 的前 $i$ 个位置）的最小交换次数。套路地写出转移：

$$f(i)=\min _{j\in [0,i)} \{f(j)+\mathrm{calc}(j+1,i)\} $$

其中 $\mathrm{calc}(l,r)$ 表示将 $[l,r]$ 值域排列成一个连续下降子段的最小交换次数。

现在的序列中，位置 $[1,l)$ 已经被值域 $[1,l)$ 占据，所以 $[1,l)$ 已经被考虑过了，不能重复计算。我们只需要考虑 $[l,n]$ 这段值域，目标是：让值域 $[l,r]$ 占据位置 $[l,r]$。

以下默认 $1\le i\neq j\le n$。

我们可以认为，操作是这么进行的：先将值域为 $[l,r]$ 的数摆在位置 $[l,r]$，再交换使其变成下降的。

将值域为 $[l,r]$ 的数染成 $0$，值域为 $(r,n]$ 的数染成 $1$，我们要让 $0$ 占据位置 $[l,n]$ 的前一段，并且 $0$ 之间不互相交换。这部分答案就是 $0,1$ 之间的逆序对数。也就是：

$$\sum_{i=1}^n \sum_{j=i+1}^n [a_i\gt r][l\le a_j\le r] $$

最后，交换成下降序列，交换次数就是顺序对数，也就是：

$$\sum_{i=1}^n\sum_{j=i+1}^n [a_i\in [l,r]][a_j\in [l,r]][a_i\lt a_j] $$

朴素地实现 $\mathrm{calc}$ 可以获得 $44$ 分。注意到：这是一个二维数点问题。例如，对于顺序对 $(i,j)$，视为 $(a_i,a_j)$ 上有一个点，那么每次查询就是查询 $(l,l)$，$(r,r)$ 为顶点的正方形内的点的数量，可以二维前缀和维护。

这样，我们就做到了 $\Theta(n^2)$。代码。