题目描述
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll A[N],B[N];
ll merge_sort(ll l,ll r)
{
    if(l>=r)return 0;                         //l>=r则返回； 
    ll mid=l+r>>1;
    ll cnt=merge_sort(l,mid)+merge_sort(mid+1,r);  //每次排序保证了左边小于右边； 
    ll i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
        if(A[i]<=A[j])B[k++]=A[i++];         //前面的序列的数较小； 
        else B[k++]=A[j++],cnt=cnt+mid-i+1;  //前面的mid-i+1个数比B[j]大； 
    while(i<=mid)B[k++]=A[i++];      
    while(j<=r)B[k++]=A[j++];                //剩下的数都比前面的大；
    for(ll i=0,j=l;j<=r;j++,i++)A[j]=B[i];   //将每个序列归并到原序列中； 
    return cnt;   //返回cnt； 
}
int main()
{
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++)cin>>A[i];
    cout<<merge_sort(0,n-1);
}