在数列 a 中,逆序对即是满足 $i< j\;and\;a_i> a_j$ 的数对。
许多情况下你推式子推着推着就推出个 $\sum_{i=1}^n \sum_{j=i+1}^n a_i> a_j$,
这就是逆序对的数量。

暴力

朴素的求法自然是 $O(n^2)$ 地枚举 i,j 统计,这里不再赘述。

归并

前置技能:归并排序。

这应该是最主流的求逆序对的方法了。

要求一个区间内的逆序对数,假设已经递归求出两个子区间的逆序对数,
接下来要做的就是求一个在左区间,一个在右区间的逆序对数。

考虑归并排序的过程,在两个指针比较大小时进行统计。

设左右区间的当前比较指针(下标)为 p1, p2,
当找到第一个 p2 使 $a_{p1}< a_{p2}$ 时,可知 $\forall i\in [p1max+1, p2),\;a_{p1}> a_{p2}$ 。
那么横跨两个子区间的以 p1 为左端点的逆序对就有 p2-p1max-1 个。
对所有 p1 统计和即可。

值得注意的是,p2>r(区间右端点)退出时,
此时左区间未处理的数对答案都有 r-p1max 的贡献因为此时左区间剩下的数都比右区间所有数大。

复杂度 $O(n \cdot log_2n)$ 。

线段树/树状数组:

前置技能:线段树(或树状数组)。

以线段树为例。

做法 1

用线段树维护区间内有效数的个数。
之所以是有效的数,是因为要从小到大删数。
如果一个数 $a_i$ 是最小的,那么以其为右端点的逆序对就是 1 至 i-1 的数的个数。

接下来呢?
在线段树中删掉最小的数(单点修改 -1),
那么第二小的数 $a_j$ 在此时就是最小的数,同样有 1 至 j-1 的数的个数(区间查询)的贡献。
以此类推从小到大一个个删数即可。

复杂度$O(n \cdot log_2n)$。

做法 2

离散化后用线段树维护一个桶。

从左到右依次计算每个数为右端点的逆序对并加入桶,即对每个数求该数左边比该数大的数的个数。
设第 i 个数左边有 $f_i$ 个比 $a_i$ 大的数,那么 $f_i$ 的值即是当前线段树上 $a_i+1~a_{max}$ 的询问。

同样复杂度是 $O(n \cdot log_2n)$。

这种做法稍稍改变可以高效解决一种特殊的问题:

对于 01 串求串中 1 的数量比 0 的数量大的区间的数量。

比较容易想到的做法是将 0 看成 -1,区间中 1 比 0(-1) 多等价于区间和大于 0 。
区间和可以转换为前缀和 s,那么 l,r 这一区间和大于 0 等价于 $s_r – s_{l-1} > 0 (r >= l)$。
移项后即是 $s_r > s_{(l-1)} (r > (l-1))$,所以题目可以转换为求前缀和的逆序对,
复杂度 $O(n \cdot log_2n)$ 。

但是 这个问题有特殊性,由 01 串的至可知相邻两个前缀和的差值一定是 1 ,
利用这一个性质可以有更高效的方法。

用做法 2 求逆序对,从左到右依次扫,对于当前 $a_i$ 一定比 $a_{i-1}$ 大 1 或者小 1,
利用到这个差值,比 $a_i$ 大的数相当于当前线段树 $a_i+1~a_{max}$ 的询问,
若 $a_i = a_{i-1}+1$ ,那么 $f_{i-1}$ 就是 $a_i~a_{maxn}$ 的询问,否则就是 $a_i+2~a_{max}$ 的询问。
那么 $f_i$ 与 $f_{i-1}$ 的差只在 $a_i$ 或 $a_i+2$ 中,长度为一,
完全没必要用线段树,用数组维护桶即可。

复杂度 $O(n)$。

分类: 问题

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: