逆序对
在数列 a 中,逆序对即是满足
暴力
朴素的求法自然是
归并
前置技能:归并排序。
这应该是最主流的求逆序对的方法了。
要求一个区间内的逆序对数,假设已经递归求出两个子区间的逆序对数, 接下来要做的就是求一个在左区间,一个在右区间的逆序对数。
考虑归并排序的过程,在两个指针比较大小时进行统计。
设左右区间的当前比较指针(下标)为 p1, p2, 当找到第一个 p2 使
值得注意的是,p2>r(区间右端点)退出时, 此时左区间未处理的数对答案都有 r-p1max 的贡献因为此时左区间剩下的数都比右区间所有数大。
复杂度
线段树/树状数组:
前置技能:线段树(或树状数组)。
以线段树为例。
做法 1
用线段树维护区间内有效数的个数。
之所以是有效的数,是因为要从小到大删数。 如果一个数
接下来呢? 在线段树中删掉最小的数(单点修改 -1), 那么第二小的数
复杂度
做法 2
离散化后用线段树维护一个桶。
从左到右依次计算每个数为右端点的逆序对并加入桶,即对每个数求该数左边比该数大的数的个数。
设第 i 个数左边有
同样复杂度是
这种做法稍稍改变可以高效解决一种特殊的问题:
对于 01 串求串中 1 的数量比 0 的数量大的区间的数量。
比较容易想到的做法是将 0 看成 -1,区间中 1 比 0(-1)
多等价于区间和大于 0 。 区间和可以转换为前缀和 s,那么 l,r
这一区间和大于 0 等价于
但是 这个问题有特殊性,由 01 串的至可知相邻两个前缀和的差值一定是 1 , 利用这一个性质可以有更高效的方法。
用做法 2 求逆序对,从左到右依次扫,对于当前
复杂度
Gitalk 加载中 ...