求重要逆序对的个数c++语言

这个问题可以使用归并排序来解决。

首先，对数组进行归并排序。在归并排序的过程中，每当两个子数组合并时，统计其中的重要逆序对个数。因为在归并排序中，左右两个子数组已经有序，所以可以使用双指针法来统计重要逆序对的个数。

具体来说，假设左右两个子数组分别为A和B，且A中的元素a和B中的元素b满足a>b。此时，B中的所有元素都是a的重要逆序对，因为它们与a的大小关系满足a>b。因此，可以将B中所有元素和a合并为一个有序数组，并将其加入到归并排序的结果中。

代码如下：

int merge(vector<int>& nums, int left, int mid, int right) {
    int i = left, j = mid + 1;
    int cnt = 0;
    vector<int> temp;
    while (i <= mid && j <= right) {
        if (nums[i] > nums[j]) {
            cnt += mid - i + 1;  // 统计重要逆序对个数
            temp.push_back(nums[j++]);
        } else {
            temp.push_back(nums[i++]);
        }
    }
    while (i <= mid) {
        temp.push_back(nums[i++]);
    }
    while (j <= right) {
        temp.push_back(nums[j++]);
    }
    for (int k = left; k <= right; k++) {
        nums[k] = temp[k - left];
    }
    return cnt;
}

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

int countImportantInversions(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}

其中，merge函数用于合并两个有序数组，并统计重要逆序对的个数。mergeSort函数用于归并排序。countImportantInversions函数是该算法的入口，用于计算重要逆序对的个数。

时间复杂度为O(nlogn)，空间复杂度为O(n)。