cpp
#include <iostream>
#include <vector>

using namespace std;



long long merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);  // 用于存储合并后的临时数组
    int i = left;  // 左子序列的指针
    int j = mid + 1;  // 右子序列的指针
    long long count = 0;  // 逆序对数目

    int k = 0;  // 临时数组的指针
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            // 当左子序列的元素大于右子序列的元素时，存在逆序对
            count += mid - i + 1;
            temp[k++] = nums[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = nums[i++];
    }

    while (j <= right) {
        temp[k++] = nums[j++];
    }

    // 将临时数组中的元素拷贝回原数组
    for (int p = 0; p < temp.size(); p++) {
        nums[left + p] = temp[p];
    }

    return count;
}

long long mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) {
        return 0;
    }

    int mid = left + (right - left) / 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];
    }

    long long count = mergeSort(nums, 0, n - 1);

    cout << count << endl;

    return 0;
}

树状数组

cpp
#include <iostream>
#include <vector>

using namespace std;

// 树状数组
class BinaryIndexedTree {
private:
    vector<int> tree;

public:
    BinaryIndexedTree(int size) {
        tree.resize(size + 1, 0);
    }

    void update(int index, int delta) {
        while (index < tree.size()) {
            tree[index] += delta;
            index += lowbit(index);
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowbit(index);
        }
        return sum;
    }

private:
    int lowbit(int x) {
        return x & (-x);
    }
};

long long countInversions(vector<int>& nums) {
    int n = nums.size();
    BinaryIndexedTree bit(n);
    vector<int> sortedNums = nums;
    sort(sortedNums.begin(), sortedNums.end());

    long long count = 0;
    for (int i = n - 1; i >= 0; i--) {
        int index = lower_bound(sortedNums.begin(), sortedNums.end(), nums[i]) - sortedNums.begin() + 1;
        count += bit.query(index - 1);  // 查询小于当前数的元素个数
        bit.update(index, 1);  // 更新树状数组中的对应位置
    }

    return count;
}

int main() {
    int n;
    cin >> n;

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

    long long count = countInversions(nums);

    cout << count << endl;

    return 0;
}