M02299:Ultra-QuickSort

merge sort, http://cs101.openjudge.cn/practice/02299/

思路：问题等价于求逆序数，写一个递归函数即可，用时约25min（又去写bug去了）

#include <iostream>
#include <vector>
using namespace std;

long long merge_count(vector<long long>& a, int left, int right) 
{
    if (left >= right) return 0;
    int mid = (left + right) / 2;
    long long count = 0;
    count += merge_count(a, left, mid);
    count += merge_count(a, mid + 1, right);

    vector<long long> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) 
    {
        if (a[i] <= a[j]) temp.push_back(a[i++]);
        else 
        {
            temp.push_back(a[j++]);
            count += (mid - i + 1); // 左边剩下的都比a[j]大
        }
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= right) temp.push_back(a[j++]);
    for (int k = 0; k < temp.size(); k++) 
        a[left + k] = temp[k];
    return count;
}

int main() 
{
    int n;
    while (cin >> n && n != 0) 
    {
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        long long ans = merge_count(a, 0, n - 1);
        cout << ans << "\n";
    }
    return 0;
}