一本通-1237：求排列的逆序数（逆序数问题）

【题目描述】 在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足jik，那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

【输入】 第一行是一个整数n，表示该排列有n个数（n ≤ 100000)。

第二行是n个不同的正整数，之间以空格隔开，表示该排列。

【输出】 输出该排列的逆序数。

【输入样例】 6 2 6 3 4 5 1

【输出样例】 8

---

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> num(100005), tmp(100005);
long long cnt = 0;

void merge(int leftStart, int rightStart, int rightEnd)
{
    int len = rightEnd - leftStart + 1;
    int i = leftStart;
    int leftEnd = rightStart - 1;

    int pos = leftStart;
    while (leftStart <= leftEnd && rightStart <= rightEnd) {
        if (num[leftStart] <= num[rightStart]) {
            tmp[pos++] = num[leftStart++];
        }
        else {
            cnt += leftEnd - leftStart + 1;
            tmp[pos++] = num[rightStart++];
        }
    }

    while (leftStart <= leftEnd) tmp[pos++] = num[leftStart++];
    while (rightStart <= rightEnd) tmp[pos++] = num[rightStart++];

    int count = 0;
    while (count++ < len) {
        num[i] = tmp[i];
        ++i;
    }
}

void mergeSort(int start, int end)
{
    if (start < end) {
        int mid = start + ((end - start) >> 1);
        mergeSort(start, mid);
        mergeSort(mid + 1, end);
        merge(start, mid + 1, end);
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> num[i];
    mergeSort(0, n - 1);
    cout << cnt << endl;

    return 0;
}

注意数据范围是$10^5$，需要用long long数据类型，可能存在溢出风险。