题解 | #逆序数#

题目描述：
求一个数组求逆序对的数量。
方法与解析：
直接套归并排序的板子，归并板子来自牛客笔记

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
void b_sort(int l,int r);
void bing(int ar1[],int len1,int ar2[],int len2,int ar[],int mid);
int a[N],b[N],n;
long long ans=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    b_sort(1,n);
    cout<<ans<<'\n';
    return 0;
}
void b_sort(int l,int r)
{
    if(l==r)return;
    int mid=l+r>>1;
    b_sort(l,mid);
    b_sort(mid+1,r);
    bing(a+l,mid-l+1,a+mid+1,r-mid,b,mid);
    for(int i=l;i<=r;i++)a[i]=b[i-l];
}
void bing(int ar1[],int len1,int ar2[],int len2,int ar[],int mid)
{
    int len=0,i=0,j=0;
    while(i<len1&&j<len2){
        if(ar1[i]<=ar2[j]){
            ar[len++]=ar1[i++];
        }
        else{
            ans+=len1-i;
            ar[len++]=ar2[j++];
        } 
    }
    for(;i<len1;i++)ar[len++]=ar1[i];
    for(;j<len2;j++)ar[len++]=ar2[j];
}