逆序对

例题

P1908 逆序对 - 洛谷

归并排序 \(O(n*\log n)\)树状数组 \(O(n*\log n)\)

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 ans = 0;
int a[500005];
void mergeSort(int L, int R) {
    static int b[500005];
    if (L == R) return;
    int mid = L + R >> 1;
    mergeSort(L, mid);
    mergeSort(mid + 1, R);
    int i = L, j = mid + 1, k = 0;
    while (i <= mid && j <= R) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) {
        b[k++] = a[i++];
    }
    while (j <= R) {
        b[k++] = a[j++];
        ans += mid - i + 1;
    }
    for (int i = L ; i <= R ; i++) {
        a[i] = b[i - L];
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    mergeSort(1, n);
    cout << ans << "\n";
    return 0;
}

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[500005];
int tr[500005];
int N;
int lowbit(int x) {
    return x & -x;
}
void add(int x) {
    while (x <= N) {
        tr[x]++;
        x += lowbit(x);
    }
}
int query(int x) {
    int res = 0;
    while (x) {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<int> idx(1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    N = idx.size();
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        ans += query(N) - query(a[i]);
        add(a[i]);
    }
    cout << ans << "\n";
    return 0;
}

习题

洛谷P3157QOJ1339

P3157 [CQOI2011] 动态逆序对 - 洛谷

\(n\) 排列, 每次删去一个元素, 然后输出删除这个元素之前的逆序对的个数.

有两种做法, 使用分块可以在线, 使用CDQ分治可以离线.

分块(在线)CDQ分治(离线)

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int lowbit(int x) {
    return x & -x;
}
int n;
int tr[320][100005];
void add(int idx, int x, int k) {
    while (x <= n) {
        tr[idx][x] += k;
        x += lowbit(x);
    }
}
int query(int idx, int x) {
    int res = 0;
    while (x) {
        res += tr[idx][x];
        x -= lowbit(x);
    }
    return res;
}
int a[100005], pos[100005];
bool vis[100005];
int belong[100005], st[320], ed[320], sz[320];
i64 ans = 0;
int B;
void remove(int p) {
    int now = pos[p];
    int x = belong[now];
    for (int i = st[x] ; i < now ; i++) {
        if (vis[i]) continue;
        if (a[i] > p) ans--;
    }
    for (int i = now + 1 ; i <= ed[x] ; i++) {
        if (vis[i]) continue;
        if (a[i] < p) ans--;
    }
    vis[now] = true;
    for (int i = 1 ; i < x ; i++) {
        ans -= sz[i] - query(i, p);
    }
    for (int i = x + 1 ; i <= B ; i++) {
        ans -= query(i, p);
    }
    sz[x]--;
    add(x, p, -1);
}
int main() {
    int m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    { // 初始化
        B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
                add(i, a[j], 1);
            }
            sz[i] = ed[i] - st[i] + 1;
        }
        for (int i = 1 ; i <= n ; i++) {
            ans += i - 1 - query(B + 1, a[i]);
            add(B + 1, a[i], 1);
        }
    }
    for (int i = 1 ; i <= m ; i++) {
        int x;
        cin >> x;
        cout << ans << "\n";
        remove(x);
    }
    return 0;
}

Couleur - QOJ

给你一个长度为 \(n\) 的数组 \(a\), 接下来 \(n\) 行, 每行有一个数 \(x\) 代表每次操作删去 \(a_x\).

每次操作前, 需要输出当前连续子数组的逆序对的最大数目, 强制在线.

删除 \(a_x\), 本质上是将一个区间分成两个区间, 而且我们可以启发式, 暴力枚举求小区间的逆序对, 大区间的逆序对由合并后区间的逆序对减去,小区间的逆序对,再减去小区间对大区间的影响,最后减去 \(a_x\) 的影响即可.

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
struct Node {
    int Lrt, Rrt;
    int sum;
} tr[100005 << 5];
int tot;
int a[100005];
int update(int old, int L, int R, int pos) {
    int now = ++tot;
    tr[now] = tr[old];
    tr[now].sum++;
    if (L == R) {
        return now;
    }
    int mid = L + R >> 1;
    if (pos <= mid) {
        tr[now].Lrt = update(tr[now].Lrt, L, mid, pos);
    } else {
        tr[now].Rrt = update(tr[now].Rrt, mid + 1, R, pos);
    }
    return now;
}
int query(int QL, int QR, int L, int R, int VL, int VR) {
    if (VL > VR) {
        return 0;
    }
    if (VL <= L && R <= VR) {
        return tr[QR].sum - tr[QL].sum;
    }
    int mid = L + R >> 1;
    int res = 0;
    if (VL <= mid) {
        res += query(tr[QL].Lrt, tr[QR].Lrt, L, mid, VL, VR);
    }
    if (VR >= mid + 1) {
        res += query(tr[QL].Rrt, tr[QR].Rrt, mid + 1, R, VL, VR);
    }
    return res;
}
int rt[100005];
struct Result {
    int L, R;
    i64 res;
    friend bool operator<(const Result &x, const Result &y) {
        return x.L < y.L;
    }
};
void solve() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    tot = 0;
    for (int i = 1 ; i <= n ; i++) {
        rt[i] = update(rt[i - 1], 1, n, a[i]);
    }
    multiset<i64> ans;
    set<Result> st;
    {
        i64 res = 0;
        for (int i = 1 ; i <= n ; i++) {
            res += query(rt[0], rt[i], 1, n, a[i] + 1, n);
        }
        ans.insert(res);
        st.insert({1, n, res});
    }
    for (int i = 1 ; i <= n ; i++) {
        i64 t = 0;
        if (!ans.empty()) {
            t = *rbegin(ans);
        }
        cout << t << " ";
        i64 tx;
        cin >> tx;
        tx ^= t;
        int x = tx;
        if (i == n) break;
        auto it = st.upper_bound({x, x, -1});
        if (it == begin(st)) {
            continue;
        }
        it--;
        auto [L, R, res] = *it;
        st.erase(it);
        ans.extract(res);
        if (x - L <= R - x) {
            i64 resL = 0;
            for (int j = L ; j < x ; j++) { // 暴力计算左半部分的逆序对, 主席树快速计算左半对右半的贡献
                resL += query(rt[L - 1], rt[j], 1, n, a[j] + 1, n);
                res -= query(rt[x], rt[R], 1, n, 1, a[j] - 1);
            }
            res -= resL; // 减去左半部分的逆序对
            res -= query(rt[L - 1], rt[x], 1, n, a[x] + 1, n); // 减去 x 对左半部分的逆序对
            res -= query(rt[x], rt[R], 1, n, 1, a[x] - 1); // 减去 x 对右半部分的逆序对
            // [L, x - 1]
            if (L <= x - 1) {
                st.insert({L, x - 1, resL});
                ans.insert(resL);
            }
            // [x + 1, R]
            if (x + 1 <= R) {
                st.insert({x + 1, R, res});
                ans.insert(res);
            }
        } else {
            i64 resR = 0;
            for (int j = x + 1 ; j <= R ; j++) { // 暴力计算右半部分的逆序对, 主席树快速计算右半对左半的贡献
                resR += query(rt[j], rt[R], 1, n, 1, a[j] - 1);
                res -= query(rt[L - 1], rt[x - 1], 1, n, a[j] + 1, n);
            }
            res -= resR; // 减去右半部分的逆序对
            res -= query(rt[L - 1], rt[x], 1, n, a[x] + 1, n); // 减去 x 对左半部分的逆序对
            res -= query(rt[x], rt[R], 1, n, 1, a[x] - 1); // 减去 x 对右半部分的逆序对
            // [L, x - 1]
            if (L <= x - 1) {
                st.insert({L, x - 1, res});
                ans.insert(res);
            }
            // [x + 1, R]
            if (x + 1 <= R) {
                st.insert({x + 1, R, resR});
                ans.insert(resR);
            }
        }
    }
    cout << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

区间逆序对

请自行转到区间/逆序对专题