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

技术分享 3年前 (2023-06-02) 0 999+

关注

逆序对与原序列

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

逆序对与原序列

逆序列

假定我们有序列 (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) 的排列。

算法过程也就如此。

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

第一种方法利用 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') 一定是不下降的。也就是说我们令 (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))，讲道理是可以过的。

发表评论