算法题：求逆序对

问题描述

给定一个序列 a1,a2,…,an，如果存在 i<j 并且 ai>aj，那么我们称之为逆序对，求逆序对的数目。 注意序列中可能有重复数字。

输入格式

第一行为 n,表示序列长度，接下来的 n 行，第 i+1 行表示序列中的第 i 个数。

输出格式

所有逆序对总数。

样例

输入

4
3
2
3
2

输出

3

数据范围

N≤10^6，Ai≤10^6。

解决方案

思路

归并排序

代码

#include <iostream>

using namespace std;

const int N = 1e6;
int arr[N];
int tempArr[N];
long long ans = 0;

void merge_sort(int l, int r) {
    if (l >= r)
        return;

    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l;
    int p = l;
    int q = mid + 1;
    while (p <= mid || q <= r) {
        if (q > r || (p <= mid && arr[p] <= arr[q])) {
            tempArr[i++] = arr[p++];
        } else {
            tempArr[i++] = arr[q++];
            ans += mid - p + 1;
        }
    }

    for (int j = l; j <= r; ++j) {
        arr[j] = tempArr[j];
    }
}

int main() {

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    merge_sort(0, n - 1);
    cout << ans;

    return 0;
}