题目链接

逆序数

题目思路：归并排序的典型题

熟练运用归并排序

代码实现

#include<bits/stdc++.h>
using namespace std;
const int Max=1e5+5;
int a[Max],b[Max];
long long sum=0;
void _merge(int left,int right)
{
    if(left>=right) return;
    int mid=left+(right-left)/2,l=left,r=mid+1;
    _merge(left,mid);
    _merge(mid+1,right);
    for(int i=left;i<=right;i++)
    {
        if((a[l]<a[r]&&l<=mid)||r>right)
        {
            b[i]=a[l];
            l++;
        }
        else
        {
            b[i]=a[r];
            sum+=(mid-l+1);
            r++;
        }
    }
    for(int i=left;i<=right;i++)
        a[i]=b[i];
}
void merge_sort(int n)
{
    _merge(0,n-1);
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    merge_sort(n);
    cout<<sum<<endl;
}