逆序对的数量刷题笔记

思路

使用归并排序

在每次返回时更新增加答案数

因为归并排序的两个特点

第一使用双指针算法

第二层层返回从局部有序合并到整体有序

例如

{4 ，1 ，2 ，3}

划分到底层是四个数组 {4}，{1}，{3}, {2};

先合并{4} {1} 为{1，4}；4>1 逆序对数量+1

在合并 {3}，{2}为{ 2 ，3} 逆序对数量再+1；

此时我们获得了两个局部有序的数组

{1，4} ，{2 ，3}

将其合并成{1，2，3，4}即可整体有序

此时左指针指向1 右边的2，3 都比1大所以逆序对数量不改变

然后左指针++，指向4 右边有两个小于4 逆序对数量+2；

所以合并完成后总逆序对数量为4

而这个数量计算关系公式为res += mid - i + 1;

然后我们再每次都将res的数量更新到答案

LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

这样在每一层返回时 res的值都会被加回来

代码

#include<iostream>
using namespace std;
typedef long long LL;

const int N=1e5+10;
int q[N],tmp[N];
LL merge_sort(int q[],int l,int r){
   if(l>=r){
       return 0;
   }
   int mid=l+r>>1;
   LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

   int i=l,k=0,j=mid+1;
   while(i<=mid&&j<=r){
       if(q[i]<=q[j]){
           tmp[k++]=q[i++];
       }else{
           res += mid - i + 1;
           tmp[k++]=q[j++];

       }

   }
   while(i<=mid){
       tmp[k++]=q[i++];
   }
   while(j<=r) {
       tmp[k++]=q[j++];
   }

for (i = l, j = 0; i <= r; i ++, j ++ ) {
q[i] = tmp[j];}