归并排序求逆序对

鸣谢:感谢zyf神犇告诉了我怎么用归并排序求逆序对!
另:这是我的第一份归并排序的代码,也是第一份求逆序对的代码

1. 什么是逆序对

对于一个包含N个非负整数的数组A[1..n],如果有i < j,且A[ i ]>A[ j ],则称(A[ i] ,A[ j] )为数组A中的一个逆序对。
例如,数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2),共4个。
摘自度娘百科

2. 怎么用归并排序求逆序对

我们其实只要在归并排序的代码上加一句话就可以实现求逆序对了。

归并排序中,在合并左右两个区间时,对于右区间的每一个数字a[i],在左区间中有n[i]个比a[i]小的数字,那么n[1]+n[2]+n[3]+...就是跨越左右区间的逆序对数。而我们除了要求出跨越左右区间的逆序对数,还要求出左区间有多少对、右区间有多少对,这个我们就用递归实现。具体看代码吧,很难口头讲清楚。

3. 例题&代码

  1. 求逆序对 codvs - 1688
    传送门= ̄ω ̄=
    思路:模板题。
    代码:

  1. hzwer与逆序对 codevs - 4163
    传送门= ̄ω ̄=
    思路:同样模板题,数据大小大了10倍而已。
    代码: