使用归并排序：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 使用归并排序方法统计逆序对数量
long long mergeAndCount(vector<long long>& nums, int left, int mid, int right) {
    vector<long long> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long inv_count = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            inv_count += (mid - i + 1); // 关键统计步骤
        }
    }
    
    // 复制剩余元素
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    // 将排序后的数组复制回原数组
    for (i = left, k = 0; i <= right; i++, k++) {
        nums[i] = temp[k];
    }
    
    return inv_count;
}

long long mergeSortAndCount(vector<long long>& nums, int left, int right) {
    if (left >= right) return 0;
    
    int mid = left + (right - left) / 2;
    long long inv_count = 0;
    
    inv_count += mergeSortAndCount(nums, left, mid);
    inv_count += mergeSortAndCount(nums, mid + 1, right);
    inv_count += mergeAndCount(nums, left, mid, right);
    
    return inv_count;
}

long long countInversions(vector<long long>& a) {
    // 创建临时副本以避免修改原数组
    vector<long long> temp = a;
    return mergeSortAndCount(temp, 0, temp.size() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    for(int op = 0; op < m; op++){
        int type;
        cin >> type;
        if(type == 1) {
            // 单点修改：1 x d
            int x;
            long long d;
            cin >> x >> d;
            a[x - 1] += d;
        } else if(type == 2) {
            // 区间修改：2 l r d
            int l, r;
            long long d;
            cin >> l >> r >> d;
            for(int i = l - 1; i < r; i++){
                a[i] += d;
            }
        } else if(type == 3) {
            // 逆序对查询
            cout << countInversions(a) << "\n";
        }
    }
    return 0;
}

树状数组方法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 树状数组（Fenwick Tree）结构，用于统计频次
struct BIT {
    int n;
    vector<long long> tree;
    BIT(int n): n(n), tree(n+1, 0) {}
    
    // 单点更新：将下标 i 的值增加 delta
    void update(int i, long long delta) {
        for(; i <= n; i += i & -i)
            tree[i] += delta;
    }
    
    // 前缀查询：求下标 1 到 i 的累计值
    long long query(int i) {
        long long s = 0;
        for(; i > 0; i -= i & -i)
            s += tree[i];
        return s;
    }
};

// 利用树状数组计算当前数组 a 的逆序对总数，时间复杂度 O(n log n)
// 这里先对 a 的值进行坐标压缩，确保 BIT 数组规模不超过元素种数
long long countInversionsBIT(const vector<long long>& a) {
    int n = a.size();
    vector<long long> sorted = a;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();
    
    BIT bit(m);
    long long inv = 0;
    // 从右往左扫描，统计每个 a[i] 之前有多少元素小于它
    for (int i = n - 1; i >= 0; i--) {
        int pos = lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin() + 1;
        inv += bit.query(pos - 1);
        bit.update(pos, 1);
    }
    return inv;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    // 处理 m 次操作
    // 操作类型：
    // 1 x d   -> 单点修改：将 a[x-1] 增加 d
    // 2 l r d -> 区间修改：将区间 [l-1, r-1] 的每个元素增加 d
    // 3       -> 逆序对查询：输出当前数组 a 的逆序对总数
    for (int op = 0; op < m; op++){
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            long long d;
            cin >> x >> d;
            a[x - 1] += d;
        } else if (type == 2) {
            int l, r;
            long long d;
            cin >> l >> r >> d;
            for (int i = l - 1; i < r; i++){
                a[i] += d;
            }
        } else if (type == 3) {
            // 每次查询时，利用 BIT 动态统计当前逆序对总数
            cout << countInversionsBIT(a) << "\n";
        }
    }
    return 0;
}