基础算法 788.逆序对的数量

#include<iostream>
using namespace std;
const int N = 1e6+10;
int n;
long long cnt=0;
int q[N],tmp[N];
void count(int q[],int l,int r)
{
    if(l>=r)return ;
    int mid = (l+r)>>1;
    count(q,l,mid);
    count(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])
        {
            tmp[k++]=q[i++];
            //cnt++;
        }
        else
        {
            tmp[k++]=q[j++];
            cnt += (mid - i + 1); //这里是重点
        }
    }
    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];
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];
    count(q,0,n-1);
    cout<<cnt;
    return 0;
}

　　数组a中的i ~ mid的数组是递增数组， 触发条件是a[i] > a[j]，所以i~mid中的数字都比当前a[j]大，所以左边i ~ mid的数组中有 mid – i + 1个数比a[j] 大。