msort_special:逆序对||归并排序

逆序对：
一句话题解： 改进归并排序，当出现a[i]>=a[j]时，由于已经是两个有序数列，则i前所有的数字都能与a[j]组成逆序对，即使其在出现a[i]>=a[j]时ans+=mid-i+1
代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[101],b[101],ans;
void msort(int l,int r){
    int mid=(l+r)/2;
    if(l==r) return;
    msort(l,mid);
    msort(mid+1,r);
    for(int i=l,j=l,k=mid+1;i<=r;i++){
        if(j<=mid&&(a[j]<=a[k]||k>r)) b[i]=a[j++];
        else{
			b[i]=a[k++];
			ans+=mid-i+1;
		}
    }
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    msort(1,n);
    printf("%d",ans);
    return 0;
}

————————————————
归并排序，稳定

void Merge(int *arr, int left, int mid, int right, int *buf)
{
    int i = left;
    int j = mid+1;
    int k = 0;
    //将两组数据按顺序填入buf
    while(i<=mid && j<=right)
    {
        if(arr[i] <= arr[j])
            buf[k++] = arr[i++];
        else
            buf[k++] = arr[j++];
    }
    //将剩余的数据填入buf
    while(i <= mid)
        buf[k++] = arr[i++];
    while(j <= right)
        buf[k++] = arr[j++];

    k = 0;
    //将数据拷贝回原数组
    while(left <= right)
        arr[left++] = buf[k++];
}

void MergeSort(int *arr, int left, int right, int *buf)
{
    int mid;
    if(left < right)
    {
        mid = (left+right)/2;
        MergeSort(arr, left, mid, buf);
        MergeSort(arr, mid+1, right, buf);
        Merge(arr, left, mid, right, buf);
    }
}