可持久化线段树

• OI Wiki: https://oi-wiki.org/ds/persistent-seg/

题目	难度
LQ240615T9 小蓝的逆序对问题
LQ240629T8 升级电缆

主席树

主席树全称是可持久化权值线段树，参见 知乎讨论。

LQ240615T9 小蓝的逆序对问题

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e5 + 10, K = 22;

int n, q;
int st[K * N], L[K * N], R[K * N], idx = 1;

void build(int u = 1, int s = 0, int e = n - 1) {
    if (s == e) {
        st[u] = 0;
        return;
    }
    L[u] = idx++;
    R[u] = idx++;
    int m = (s + e) >> 1;
    build(L[u], s, m);
    build(R[u], m + 1, e);
}

int add(int i, int u, int s = 0, int e = n - 1) {
    int uu = idx++;
    if (s == e) {
        st[uu] = st[u] + 1;
        return uu;
    }
    int m = (s + e) >> 1;
    if (i <= m) {
        L[uu] = add(i, L[u], s, m);
        R[uu] = R[u];
    } else {
        L[uu] = L[u];
        R[uu] = add(i, R[u], m + 1, e);
    }
    st[uu] = st[L[uu]] + st[R[uu]];
    return uu;
}

int count(int l, int r, int ul, int ur, int s = 0, int e = n - 1) {
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) {
        return st[ur] - st[ul];
    }
    int m = (s + e) >> 1;
    return count(l, r, L[ul], L[ur], s, m)
           + count(l, r, R[ul], R[ur], m + 1, e);
}

vector<int> discretize(vector<int> &vec) {
    vector<int> sorted_vec(vec);
    std::sort(sorted_vec.begin(), sorted_vec.end());
    sorted_vec.erase(std::unique(sorted_vec.begin(), sorted_vec.end()), sorted_vec.end());

    vector<int> result;
    result.reserve(vec.size());
    for (auto &v: vec) {
        int discrete_value = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), v) - sorted_vec.begin();
        result.push_back(discrete_value);
    }
    return result;
}

int main() {
    cin >> n >> q;
    vector<int> a(n);
    for (auto &v: a) {
        cin >> v;
    }

    a = discretize(a);
    vector<int> root(n + 1);
    root[0] = 1;
    idx = 2;
    build();

    ll inv = 0;
    for (int i = 0; i < n; ++i) {
        inv += count(a[i] + 1, n - 1, root[0], root[i]);
        root[i + 1] = add(a[i], root[i]);
    }

    while (q--) {
        int i, j;
        cin >> i >> j;
        i--, j--;

        ll ans = inv;
        ans += count(a[i] + 1, n - 1, root[i + 1], root[j])
               - count(0, a[i] - 1, root[i + 1], root[j]);

        ans += count(0, a[j] - 1, root[i + 1], root[j])
               - count(a[j] + 1, n - 1, root[i + 1], root[j]);

        if (a[i] < a[j]) {
            ans++;
        } else if (a[i] > a[j]) {
            ans--;
        }
        cout << ans << endl;
    }

    return 0;
}

（全文完）