题目描述 给定1,2,…,n的一个排列，求它的逆序数。 输入 第一行是一个整数n，表示该排列有n个数（n ≤ 100000)。 第二行是n个不同的正整数，之间以空格隔开，表示该排列。 输出 输出该排列的逆序数。 注意使用O(n^2)的算法会超时。 给出C++实现

以下是使用归并排序求逆序对的C++实现：

#include <iostream>
#include <vector>

using namespace std;

long long merge(vector<int>& nums, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    vector<int> tmp(right - left + 1);
    long long count = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            count += mid - i + 1;
            tmp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    for (int i = 0; i < k; i++) {
        nums[left + i] = tmp[i];
    }
    return count;
}

long long mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = (left + right) / 2;
    long long count = 0;
    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);
    count += merge(nums, left, mid, right);
    return count;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << mergeSort(nums, 0, n - 1) << endl;
    return 0;
}

该算法的时间复杂度为O(nlogn)，可以通过本题。