51Nod--1019 逆序数

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 50010;
int a[N];
int b[N];
int sum = 0;

// 合并左右两边的数组元素，数组元素的交换在这里进行 
void merge(int left, int mid, int right) {
    int i = left;
    int j = mid+1;
    int index = 0;
    // 进行左右两边的元素合并 
    for(; i <= mid && j <= right; ) {
        if(a[i] <= a[j]) { // 从小到大排序 
            b[index++] = a[i++];
        } else {
            b[index++] = a[j++];
            sum += mid-i+1; // 逆序数增加，这里是核心代码 
        }
    }
    // 当有一边中的元素全部用完之后，将剩下的那一边元素直接复制 
    while(i <= mid) {
        b[index++] = a[i++];
    }
    while(j <= right) {
        b[index++] = a[j++];
    }
    // 将合并好了的数组元素复制到原来的数组中 
    for(int k = 0; k < index; k++) {
        a[left++] = b[k];
    }
}

// 递归进行反复合并，实现排序，数组下标范围：[left, right] 
void mergeSort(int left, int right) {
    // 当剩下的未合并的元素至少为两个的时候，合并这两个元素
    if(left < right) { 
        int mid = (right + left) / 2;
        mergeSort(left, mid);
        mergeSort(mid+1, right);
        merge(left, mid, right);
    }
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        scanf("%d", a+i);
    }

    mergeSort(0, n-1);

    cout << sum << endl;

    return 0;
}