算法学习(22): 逆序对与原序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法学习(22): 逆序对与原序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

逆序对与原序列

在《组合数学》中有这么一个从逆序列构建一个排列的过程……而刚好有一场考试有考了类似的问题，于是在此总结一下。

逆序对与原序列
- 逆序列
- 逆序个数
- 带修改问题
- 冒泡排序
  - 交换次数
  - 循环次数

逆序列

假定我们有序列 \(P\) 是 \(\{1, 2, \cdots, n\}\) 的一个排列。如果 \(i < j\) 并且 \(p_i > p_j\) 则称数对 \((p_i, p_j)\) 为一个逆序对。

在逆序列中，我们令 \(r_k\) 表示 \(p_j = k\) 的逆序对数量。

注意是数值，而非下标！！！

例子：排列 \(31524\) 的逆序列为 \(1, 2, 0, 1, 0\)。

解释：数字 \(1\) 前有一个数比他大，\(2\) 前有两个……所以为 \(1, 2, 0, 1, 0\)。

我们不难得知：\(0 \le r_i \le n - i\)。依据乘法原理，我们可知 \(r_i\) 一共有 \(n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!\) 种。

这提示我们，逆序列与排列一一对应，也就是说，唯一的逆序列可以产生唯一的排列。

那么下面描述两种方法通过逆序列构建一个排列。

算法一：相对插入法

我们令初始序列 \(P\) 为空，逆序考虑 \(k\) （\(k\ from\ n \ downto \ 1\))，重复以下步骤：

考虑 \(r_k\)，由于 \((k, n]\) 都已经放好，那么可知剩下的数其实对其没有影响。于是我们只需要将 \(k\) 放在第 \(r_k\) 个数后面即可。这样一定可以保证数 \(k\) 前有 \(r_k\) 个比他大的数。

在这个算法中，我们只做到了这些整数的相对位置不变，但是在排列中的位置是不知道的。

于是我们可以考虑下一个算法。

算法二：绝对插入法

我们先构造 \(n\) 个空位。从 \(1 \sim n\) 考虑 \(r_k\)。

因为 \(k\) 前面应该还有 \(r_k\) 个大于 \(k\) 的整数，而且这些数都还没有插进来，因此，必须给这些数留出 \(r_k\) 个空位。于是我们在第 \(r_k + 1\) 的空位上放上数 \(k\)。

举个例子：求逆序为 \(1, 2, 0, 1, 0\) 的排列。

算法学习(22): 逆序对与原序列

算法过程也就如此。

说了两种方法，到底哪一种可行性更高？

第一种方法利用 vector 可以很快的写出来，但是复杂度还是近似于 \(O(n^2)\)。利用平衡树可以把他优化到 \(O(n \log n)\) 的复杂度。

而第二种方法，不太好写，朴素还是 \(O(n^2)\) 的复杂度。可以利用线段树和二分做到 \(O(n \log n)\) 的复杂度，只是不太直观。（用树状数组也行，\(O(n \log^2 n)\) 但常数极小。也非常优秀）。

不过如果我们只需要求其中值的位置呢？

我们还是考虑相对插入算法。首先令 \(b = r_k\)，表示 \(k\) 在当前时候前面有几个数。

那么能够做出贡献的只有 \(r_i, i \in [1, k)\)。我们模仿插入的过程逆序考虑：

如果 \(r_i \le b\)，意味着 \(i\) 会插入到 \(k\) 前面，故令 \(b = b + 1\)。
否则不改变 \(b\)

最终 \(b\) 的大小也就是 \(k\) 所在的位置。

这个算法是 \(O(n)\) 的，也启发我们有另外一种 \(\Theta(n^2)\) 的写法。

再来一个问题：求某一个位置的值？

这一问题作为练习，留给读者思考（还是考虑 \(O(n)\) 做？）

逆序个数

很多时候，出题人并不会基于这种描述方法，而是采用下标来表示。

逆序个数序列 \(b_i\) 表示 \(\sum_{j < i}[p_j > p_i]\)，也就是第 \(i\) 个数前有几个数比它大。

我们可以稍加改变前文中的两个算法，从而得到求逆序的一种方法。

这里讲一下基于相对插入法的做法吧。

相对插入法

还是类似的，令初始序列为空，从前向后考虑下表 \(i\)：

我们将 \(i\) 放在从后向前 \(b_i\) 个数前（若 \(b_i = 0\)，则直接放在末端）

注意，是直接放下标

于是最终序列 \(a_i = rank(i)\)，也就是 \(i\) 从前向后数的位置。

那么这里考虑某一个位置的值？

我们从前向后考虑，令 \(r\) 表示在序列中 \(i\) 后面的数的个数，考虑什么时候 \(b_j\) 会对 \(r\) 做出贡献？若 \(b_j \le r\)，那么意味着 \(j\) 会放在 \(i\) 的右侧，那么此时令 \(r = r + 1\)。

于是最终 \(a_i = n - r\)。

于是我们有了 \(\Theta(n^2)\) 的做法了……

带修改问题

考虑这样一个问题：对于逆序对序列 \(b_i\)，要求支持单点修改 \(b_i\)，以及单点查询 \(a_i\)。

原题为 CF1540D

这道题需要用到分块。

考虑以下事实：

对于一定的序列 \(b_i\)，如果初始值为 \(r\)，则经过操作后 \(r \to r'\) 的结果是一定的。这启发我们可以分块。
而考虑对于每一个 \(r \in [1, n]\)，对应的结果 \(r'\) 一定是不下降的。也就是说 \(r\) 越大，\(r'\) 越大。~~也就是说我们令 \(f(r)\) 表示 \(r\) 经过了序列之后变成的值，\(f\) 是一个单调不下降序列。~~

于是对于每一块，考虑用线段树（或者树状数组等神秘数据结构）维护（需要支持区间加和二分求某个值的位置），初始 \(T_i= i\)。

按顺序加入 \(b_j\)，考虑先找到所有 \(\ge b_j\) 的 \(T_i\) ，并整体加 \(1\)。不难发现，其实每一次只是后缀 \(+1\)，又由于原序列的单调的，所以新的序列是单调，这为二分查找提供了保障。

补充一下关于使用树状数组这件事。

复杂度为 \(O(B \log^2 n)\) 是单纯的二分 + 树状数组。然而如果使用树状数组上二分的操作可以避免一个 \(\log\)，也就是复杂度成为 \(O(B \log n)\)。这样可以过。

提交：https://codeforces.com/contest/1540/submission/211432601

于是我们可以在 \(O(B \log n)\) 的复杂度中处理出 \(T_i\)，并可以在 \(O(\log n)\) 内找到变换对应的值。于是查询的复杂度为 \(O(\frac nB \log n)\)。

考虑修改？暴力重构每一块就是了。修改为 \(O(B \log n)\)。

块长设为 \(\sqrt n\) 即可，总复杂度为 \(O(n \sqrt n \log n)\)。毕竟是 5s 时限，还是可以过的。

然而会有更优秀的做法，参考：CF1540D. Inverse Inversions - jz_597 - 博客园

虽然我看不懂它……

冒泡排序

这属于是逆序对经典的问题来源了。

由于我太菜，很多东西我可能不知道，如果有什么可以补充或者建设性的建议请留言 QwQ

交换次数

利用冒泡排序将一个无序序列排成有序序列需要多少次交换？

首先观察每次交换中改变的量，很难发现，每次逆序对会减一。

考虑每次交换的是 \(P_i \gt P_{i + 1}\) 的位置，交换之后，对于 \(P_{i + 1}\) 前比它大的数就会减少一个 \(P_i\)，而对于 \(P_i\) 没影响，所以总体逆序对会 \(-1\)。

于是我们每次排序都可以将逆序对数 \(-1\)，于是总交换次数其实就是逆序对数。

循环次数

冒泡排序我们常常有一个小小的优化：

for (int i = 0; i <= n; ++i) {
	bool swaped = false;
	for (int j = 1; j < n; ++j) {
		if (P[i] > P[i + 1]) swap(P[i], P[i + 1]), swaped = true;
	}
	if (!swaped) break;
}

注意 \(i\) 从 \(0\) 开始，这里的循环次数也就是指在最后一行 break 时 \(i\) 的大小，我们怎么求？

其实这里有两个结论：

如果这个序列是一个排列，那么循环次数 \(= \max(i - P_i)\)，考虑每次扫一遍，如果 \(P_i < i\)，那么这个数必定向前走一步，考虑前面必定有一个 \(> P_i\) 的数会过来与它交换。
对于一般的序列，设 \(inv_i\) 表示第 \(i\) 个数前比他大的数的个数（也就是逆序个数序列），那么循环次数是 \(\max(inv_i)\)。首先不难证明这个结论在排列中与 \(\max(i - P_i)\) 等价，考虑类似的如何在一般序列上证明。如果 \(inv_i > 0\)，那么意味着前面一个有一个比它大的数，也就意味着这一次扫一定可以将一个前面的数扫到后面去，使得 \(inv_i \leftarrow inv_i - 1\)。所以扫的次数即 \(inv_i\) 的上界，也就是 \(\max(inv_i)\)。