逆序对的数量详细解析

C++ 代码

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;
const int N=100100;
int a[N],temp[N];
int n;
LL res;
void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);

    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r) 
    {
        if(a[i]<=a[j]) temp[k++]=a[i++];
        else
        {
            res+=mid-i+1;
            temp[k++]=a[j++];
        }
    }
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++) a[i]=temp[j];
}
int main(void)
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    merge_sort(a,0,n-1); 
    cout<<res;
    return 0;
}

为啥 res+=mid-i+1 ？ 这是因为:
数组a中的i ~ mid的数组是递增数组， 触发条件是a[i] > a[j]，所以i~mid中的数字都比当前a[j]大，
所以左边i ~ mid的数组中有 mid - i + 1个数比a[j] 大