题解 | 归并排序模板运用

s

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int k[N];
long long res=0;
void merge_sort(int*nums,int left,int right)
{
    if(left>=right)return;
    int mid=left+right>>1;
    merge_sort(nums,left,mid);
    merge_sort(nums,mid+1,right);
    int l=left,r=mid+1;
    int count=0;
    while(l<=mid && r<=right)
    {
        if(nums[l]<nums[r])
        {
            k[count++]=nums[l++];
        }
        else
        {
            k[count++]=nums[r++];
            res=res+mid-l+1;
        }
    }
    while(l<=mid)k[count++]=nums[l++];
    while(r<=right)k[count++]=nums[r++];
    for(int l=left,j=0;l<=right;l++,j++)
    {
        nums[l]=k[j];
    }
}
int main()
{
    int n;cin>>n;
    int arr[N];
    for(int i=0;i<n;i++)cin>>arr[i];
    merge_sort(arr,0,n-1);
    cout<<res<<endl;
    return 0;
}