逆序对与原序列


逆序列

假定我们有序列 \(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): 逆序对与原序列-LMLPHP

算法过程也就如此。


说了两种方法,到底哪一种可行性更高?

第一种方法利用 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\)

这道题需要用到分块。

考虑以下事实:

  • 对于一定的序列 \(b_i\),如果初始值为 \(r\),则经过操作后 \(r \to r'\) 的结果是一定的。这启发我们可以分块。

  • 而考虑对于每一个 \(r \in [1, n]\),对应的结果 \(r'\) 一定是不下降的。也就是说我们令 \(f(r)\) 表示 \(r\) 经过了序列之后变成的值,\(f\) 是一个不严格单调上升序列。

于是对于每一块,考虑用线段树维护(支持区间加和二分求某个值的位置),初始 \(T_i= i\)

在加入 \(b_j\) 是,考虑先找到所有 \(\ge b_j\)\(T_i\) ,并整体加 \(1\)。不难发现,其实每一次只是后缀 \(+1\),而原序列的单调的,所以新的序列是单调,这为线段树上二分查找提供了充分的条件。(其实还是可以用二分的树状数组,只是复杂度为 \(O(B \log^2 n)\),还是常数很小)

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

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

块长设为 \(\sqrt n\) 即可,总复杂度为 \(O(n \sqrt n \log n)\),讲道理是可以过的。

05-31 21:37