算法学习(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\) 的排列。
算法过程也就如此。
说了两种方法，到底哪一种可行性更高？
第一种方法利用 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)\)，讲道理是可以过的。