逆序对

在数列 a 中,逆序对即是满足 i<jai>aj 的数对。 许多情况下你推式子推着推着就推出个 i=1nj=i+1nai>aj, 这就是逆序对的数量。

暴力

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

归并

前置技能:归并排序。

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

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

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

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

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

复杂度 O(nlog2n)

线段树/树状数组:

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

以线段树为例。

做法 1

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

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

复杂度O(nlog2n)

做法 2

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

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

同样复杂度是 O(nlog2n)

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

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

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

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

用做法 2 求逆序对,从左到右依次扫,对于当前 ai 一定比 ai1 大 1 或者小 1, 利用到这个差值,比 ai 大的数相当于当前线段树 ai+1amax 的询问, 若 ai=ai1+1 ,那么 fi1 就是 aiamaxn 的询问,否则就是 ai+2amax 的询问。 那么 fifi1 的差只在 aiai+2 中,长度为一, 完全没必要用线段树,用数组维护桶即可。

复杂度 O(n)