写出利用分治法计算整数序列x,x2…x„中逆序对个数的程序，注释清楚程序中每个变量的含义。用C++写

#include <iostream>
using namespace std;

// 函数用于计算数组中逆序对的数量，采用分治策略递归实现
int countInversions(int arr[], int left, int right) {
    // base case: 如果只有一个元素或没有元素，逆序对数量为0
    if (left == right)
        return 0;
    
    // 计算中间位置
    int mid = (left + right) / 2;
    
    // 分治求解左半部分和右半部分逆序对数量，并将结果相加
    int inversionsLeft = countInversions(arr, left, mid);   // 左半部分逆序对
    int inversionsRight = countInversions(arr, mid + 1, right);  // 右半部分逆序对
    
    // 遍历整个数组，对于每个右侧元素，它与左侧所有比它小的元素形成逆序对
    int inversionsCrossing = 0;  // 跨越中点的逆序对
    for (int i = left; i <= mid; ++i) {
        for (int j = mid + 1; j <= right; ++j) {
            if (arr[i] > arr[j])  // 当左侧元素大于右侧元素时，增加一个逆序对计数
                inversionsCrossing++;
        }
    }

    // 返回左右两部分的逆序对总数加上跨越中点的逆序对数
    return inversionsLeft + inversionsRight + inversionsCrossing;
}

int main() {
    int n;
    cout << "请输入数组的长度: ";
    cin >> n;
    int x[n];  // 存储输入的整数序列
    cout << "请输入整数序列: ";
    for (int i = 0; i < n; ++i)
        cin >> x[i];

    // 调用函数并输出逆序对总数
    int inversionCount = countInversions(x, 0, n - 1);
    cout << "数组中有 " << inversionCount << " 个逆序对。\n";

    return 0;
}

在这个程序中，
- `countInversions` 函数是主的分治算法，接收一个数组、起始索引和结束索引作为参数。
- `inversionsLeft` 和 `inversionsRight` 分别表示左半部分和右半部分的逆序对数量。
- `inversionsCrossing` 计算的是跨越中点的逆序对数。
- `main` 函数中获取用户输入的数组，调用 `countInversions` 并打印结果。