【解题报告】P7406 [JOI 2021 Final] 集合写真

· · 题解

找出性质 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)。代码。