分治法求逆序对个数(归并排序)

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e4;
int n;
int a[maxn], t[maxn];

void read()
{
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
}

int countReversefewByMergeSort(int arr[], int left, int right, int tempArr[])
{
    int cnt = 0;
    if(left < right)
    {
        int mid = left + (right-left)/2;
        cnt += countReversefewByMergeSort(arr, left, mid, tempArr);
        cnt += countReversefewByMergeSort(arr, mid+1, right, tempArr);
        int i = left, j = mid, k = left;
        while(i < mid || j < right)
        {
            if(j >= right || (i < mid && arr[i] <= arr[j]))
                tempArr[k++] = arr[i++];
            else
            {
                tempArr[k++] = arr[j++];
                cnt += mid-i;
            }
        }
        for(k = left; k < right; ++k)
            arr[k] = tempArr[k];
    }
    return cnt;
}

void solve()
{
    cout << countReversefewByMergeSort(a, 0, n, t);
}

int main()
{
    read();
    solve();
    return 0;
}