逆序对

归并排序求逆序对

在归并的过程中我们需要进行两个区间之间的比较
如果出现逆序对就要交换，因此在归并本身就可以直接求逆序对的个数
如果出现左区间中的某个数 i 大于右区间的某个数 j
那么我们由这个数可以得到 mid - i + 1 个逆序对
算入最终答案 ans 即可

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+15;
int a[N],t[N];
long long ans=0;
int n;
void Merge(int l,int r){
    if(l>=r) return;
    int mid=(l+r)/2,k=l;
    Merge(l,mid),Merge(mid+1,r);
    int i=l,j=mid+1;
    while(i<=mid&&j<=r){
	if(a[i]<=a[j]) t[k++]=a[i++];
	else{
	    t[k++]=a[j++];
	    ans+=(mid-i+1);
	}
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=t[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    Merge(1,n);
    printf("%lld",ans);
    return 0;
}