P1327 数列排序

问题

P1327 数列排序
给定一个元素互不相同的序列，每次可以任意交换两个位置，求将从小到大排序的最小操作次数。
数据规模：$n \le 1e5$，$-2^{31} < a_{i} < 2^{31}-1$。

首先，我联想到 LIS题型整理。

由于序列中的元素互不相同，可以把每个元素映射成它在排序后序列中的位置，从而将原序列转化为一个排列，同时完成值域压缩。

最开始我猜测答案可能是：$n - LIS(A)$，但这是不对的。

LIS 研究的是能够保持不变的相对顺序，通常对应“删除元素”或“取出一个元素后重新插入”等操作；本题允许交换任意两个位置，一次操作会同时改变两个元素的位置，因此需要研究的是元素目标位置之间的关系。

转化为排列

将原数组中的每个元素替换成它在有序数组中的排名，这是我尝试的一种映射方案；

A : 3 5 2 4 7 1 6 8
B : 1 2 3 4 5 6 7 8

这里 $A_i$ 表示：当前位置 $i$ 上的元素，排序后应该移动到位置 $A_i$。

因为所有元素互不相同，每个元素恰好有一个对应位置，每个目标位置恰好对应一个元素；

因此，这是一一映射，$A$ 是一个 $1\sim n$ 的排列。

把每个位置向其目标位置连边：$i\to A_i$，由于每个位置有唯一的后继，最终一定会回到已经出现的位置。同时，每个位置的前驱是唯一的，所以不会出现分支，也就不会出现树了，最终只会形成若干个环。

这题应该属于 [[置换]] 相关内容，不在本篇中展开。

样例的这个排列就可以分解为：$1\to3\to2\to5\to7\to6\to1$，以及两个长度为 $1$ 的换 $4 \to 4, 8 \to 8$，所以一共有 $3$ 个环，长度分别为 $6, 1, 1$。

一个环需要几次交换

考虑一个长度为 $k$ 的环：$v_{1} \to v_{2} \to \dots \to v_{k} \to v_{1}$。

它表示位置 $v_{1}$ 上的元素应该去 $v_{2}$，位置 $v_{2}$ 上的元素应该去 $v_{3}$，以此类推，位置 $v_{k}$ 上的元素应该去 $v_{1}$。

因为 $v_{k}$ 上的元素正是位置 $v_{1}$ 所需要的元素。交换 $v_{1}$ 和 $v_{k}$ 后，位置 $v_{1}$ 顺利归位，剩下的错误位置形成一个长度为 $k-1$ 的环：$v_{k} \to v_{2} \to \dots \to v_{k-1} \to v_{k}$。

所以每次操作都能固定一个位置，一个长度为 $k$ 的环，共需要交换 $k-1$ 次。

统计答案

设共有 $c$ 个环，长度分别为 $k_{1}, k_{2}, \dots, k_{c}$，那么 $k_{1} + k_{2} + \dots + k_{c} = n$。

答案就是 $\sum_{i=1}^{c}(k_{i}-1) = n - c$。

所以非常神奇的是，最少任意交换次数 = 总点数 - 排列的环数。

当然也可以从并查集的视角看这个问题，答案就是：总点数 - 连通块数量。

不过并查集只是一个实现的工具而已，更本质的数学推导还是置换环与变换操作之间的关系。

注意区分几个类似概念：LIS模型 | [[逆序对]]。