求逆序对（C++）

分治算法和归并排序。

思路：归并排序是分治的思想，依据归并排序的框架，在出现逆序对时更新总数即可。

代码如下：

#include <iostream>
using namespace std;

long long ans = 0;

void merge(int a[], int left, int right)
{
    if (left == right) return;
    int mid = (left + right) / 2;
    int i = left, j = mid + 1, k = left;
    int *temp = new int[right - left + 1];
    merge(a, left, mid);
    merge(a, mid + 1, right);
    while (i <= mid && j <= right)
    {
        if (a[i] < a[j]) temp[k++] = a[i++];
        else 
        {
            temp[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int i = left; i <= right; ++i) a[i] = temp[i];
}

int main()
{
    int n; cin >> n;
    int *a = new int[n + 1];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    merge(a, 1, n);
    cout << ans << endl;
}