题解 - 帖子 - CQUPT OJ

（赛时不会真有人直接调用函数吧）

思路

认真观察就会发现，等价于求算数组的逆序对，因为对于数组中的任意一个逆序对都会对产生的贡献.

求算数组逆序对的方法有很多，比如归并排序。然而在本题中，采用归并排序只能求算出原始数组的逆序对，然而本题不太适用，因为当新增一个元素时，需要统计原数组中的大于的元素个数，记为，那么新数组的逆序对增量就是。总言之，归并排序不方便统计新增元素后的逆序对增量。

正解是采用树状数组或线段树求算数组的逆序对数量，且该数据结构也方便处理更新操作。上述问题属于很经典的问题了，初学者请参考视频树状数组 P1908 逆序对.

Code

#include <bits/stdc++.h>
using namespace std;

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 2) {}  // 防止越界

    void update(int idx, int delta) {
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

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

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

    vector<int> all_vals = a;
    all_vals.insert(all_vals.end(), x_list.begin(), x_list.end());

    sort(all_vals.begin(), all_vals.end(), greater<int>());
    auto last = unique(all_vals.begin(), all_vals.end());
    all_vals.erase(last, all_vals.end());

    FenwickTree ft(all_vals.size());

    auto get_rank = [&](int x) {
        int pos = lower_bound(all_vals.begin(), all_vals.end(), x, greater<int>()) - all_vals.begin();
        return pos + 1;
    };

    long long total = 0;
    for (int num : a) {
        int r = get_rank(num);
        total += ft.query(r - 1);
        ft.update(r, 1);
    }

    cout << total << '\n';

    for (int x : x_list) {
        int r = get_rank(x);
        total += ft.query(r - 1);
        ft.update(r, 1);
        cout << total << '\n';
    }

    return 0;
}