C++ 代码

#include<iostream>
using namespace std;
const int N=1000010;
int arr[N];
long long result;//结果可能超过int的范围，用longlong类型
/*
我们将序列从中间分开，将逆序对分成三类：
1、两个元素都在左边；
2、两个元素都在右边；
3、两个元素一个在左一个在右；
*/
void merge_sort(int arr[],int l,int r)//采用排序的原因是可以求得左元素在所有的右逆序数
{
    if (l>=r)return ;
    int k=0,temp[N];
    int mid=l+r>>1,i=l,j=mid+1;
    merge_sort(arr,l,mid);//左半逆序数数量
    merge_sort(arr,mid+1,r);//右半逆序数数量
    while(i<=mid&&j<=r)
    {
        //因为左右两部分逆序数的数量已经求出，所以只需要计算第三种情况
        if (arr[i]<=arr[j])//右大于等于左，只需排序
        {
            temp[k++]=arr[i++];
        }
        else//左大于右，结果加上左边大于该右元素的所有元素的数量(不能加上所有右小于等于该左元素的数的数量，会重复计算)
        {

            temp[k++]=arr[j++];
            //result+=j-mid;
            result+=(mid-i+1);//左边大于该右元素的所有元素的数量
        }
    }
    while(i<=mid)temp[k++]=arr[i++];
    while(j<=r)temp[k++]=arr[j++];
    for(int i=l,k=0;i<=r;i++)
    {
        arr[i]=temp[k++];
    }
    /*如果选择倒着赋值k需要--，因为k多加了一个1
    k--;
    for(int i=r;i>=l;i--)
    {
        arr[i]=temp[k--];
    }
    */
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    merge_sort(arr,0,n-1);
    printf("%lld",result);
    return 0;
}