归并排序模板

以后可能会有更详细介绍

#include
    
     #include
     
      const int N=5e5+100;using namespace std;int n,a[N],b[N];long long num;void msort(int l,int r){    if (l==r) return ;    int mid=(l+r)>>1;    msort(l,mid);    msort(mid+1,r);    int i=l,j=mid+1,k=l;    while (i<=mid&&j<=r)    if (a[i]<=a[j]) b[k++]=a[i++];    else    {        num=num+mid-i+1;    //  求逆序对        b[k++]=a[j++];    }    while (i<=mid) b[k++]=a[i++];    while (j<=r) b[k++]=a[j++];    for (int i=l;i<=r;i++) a[i]=b[i];    return ;}int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)    scanf("%d",a+i);    msort(1,n);    for (int i=1;i<=n;i++)    printf("%d ",a[i]);    printf("\n");    printf("%lld",num);     //输出逆序对    return 0;}