题目描述

rt，思路看大佬写的，用归并排序求逆序对个数

样例

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

void solve(vector<int> & a)
{
    int a_end(a.size());
    long long count(0);
    vector<int> t(a_end);
    for (int block = 1; block < a_end; block *= 2) {
        for (int i = 0; i < a_end; i += 2*block) {
            int l(i), r(i+block), j(i), l_end(min(i+block, a_end)), r_end(min(i+2*block, a_end));
            while (l < l_end || r < r_end) {
                if (l >= l_end || (r < r_end && a[r] < a[l])) {
                    t[j++] = a[r++];
                    count += l_end - l;
                }
                else
                    t[j++] = a[l++];
            }
        }
        a = t;
    }
    cout << count << endl;
}

int main()
{
    int N, ai;
    while (true) {
        cin >> N;
        if (N == 0)
            break;
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
            cin >> ai;
            a[i] = ai;
        }

        solve(a);
    }

    return 0;
}