分治算法——逆序对

#include <iostream>

using namespace std;

typedef long long ll;

int a[500010], b[500010];
int num;

void merge_sort(int left, int right)
{
    if (left == right)
        return;
    int mid = (left + right) / 2;
    int i = left, j = mid+1, k = left;
    merge_sort(i, mid);
    merge_sort(j, right);
    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
            b[k++] = a[i++]; 
        else
        {
            b[k++] = a[j++];
            int m = mid - i;
            m += 1;
            num += m;
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= right)b[k++] = a[j++];

    for (int l = left; l <= right; l++)
        a[l] = b[l];

}



int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    merge_sort(1, n);
    cout << num << endl;
    return 0;
}