逆序对与原序列
在《组合数学》中有这么一个从逆序列构建一个排列的过程……而刚好有一场考试有考了类似的问题,于是在此总结一下。
-
逆序对与原序列
- 逆序列
- 逆序个数
- 带修改问题
逆序列
假定我们有序列 (P) 是 ({1, 2, cdots, n}) 的一个排列。如果 (i 并且 (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 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)),讲道理是可以过的。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net