可持久化线段树

例题

洛谷P3919

代码

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;
}();
const int N = 1000005;
struct Node {
    int Lrt, Rrt;
    int sum;
} tr[N << 5];
int tot;
int a[N];
int build(int L, int R) {
    int now = ++tot;
    if (L == R) {
        tr[now].sum = a[L];
        return now;
    }
    int mid = L + R >> 1;
    tr[now].Lrt = build(L, mid);
    tr[now].Rrt = build(mid + 1, R);
    return now;
}
int update(int old, int L, int R, int pos, int k) {
    int now = ++tot;
    tr[now] = tr[old];
    if (L == R) {
        tr[now].sum = k;
        return now;
    }
    int mid = L + R >> 1;
    if (pos <= mid) {
        tr[now].Lrt = update(tr[now].Lrt, L, mid, pos, k);
    } else {
        tr[now].Rrt = update(tr[now].Rrt, mid + 1, R, pos, k);
    }
    return now;
}
int query(int old, int L, int R, int pos) {
    if (L == R) {
        return tr[old].sum;
    }
    int mid = L + R >> 1;
    if (pos <= mid) {
        return query(tr[old].Lrt, L, mid, pos);
    } else {
        return query(tr[old].Rrt, mid + 1, R, pos);
    }
}
int rt[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    rt[0] = build(1, n);
    for (int i = 1 ; i <= m ; i++) {
        int v, op, loc;
        cin >> v >> op >> loc;
        if (op == 1) {
            int value;
            cin >> value;
            rt[i] = update(rt[v], 1, n, loc, value);
        } else {
            rt[i] = rt[v];
            cout << query(rt[i], 1, n, loc) << "\n";
        }
    }
    return 0;
}

主席树

静态区间第 k 小

例题

P3834 【模板】可持久化线段树 2 - 洛谷

代码

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;
}();
const int N = 200005;
struct Node {
    int Lrt, Rrt;
    int sum;
} tr[N << 5];
int tot;
int a[N];
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 pos) {
    if (L == R) {
        return L;
    }
    int mid = L + R >> 1;
    int cnt = tr[tr[QR].Lrt].sum - tr[tr[QL].Lrt].sum;
    if (pos <= cnt) {
        return query(tr[QL].Lrt, tr[QR].Lrt, L, mid, pos);
    } else {
        return query(tr[QL].Rrt, tr[QR].Rrt, mid + 1, R, pos - cnt);
    }
}
int rt[N];
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> idx(1, -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);
    }
    for (int i = 1 ; i <= n ; i++) {
        rt[i] = update(rt[i - 1], 1, n, a[i]);
    }
    for (int i = 1 ; i <= m ; i++) {
        int L, R, k;
        cin >> L >> R >> k;
        cout << idx[query(rt[L - 1], rt[R], 1, n, k)] << "\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;
}();
const int N = 200005;
struct Node {
    int Lrt, Rrt;
    int sum;
} tr[N << 5];
int tot;
int a[N];
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;
}
vector<int> idx(1, -1);
int query(int QL, int QR, int L, int R, int pos) {
    if (R < pos) {
        return tr[QR].sum - tr[QL].sum;
    }
    if (L == R) {
        return 0;
    }
    int mid = L + R >> 1;
    int rk = 0;
    if (pos >= L) {
        rk += query(tr[QL].Lrt, tr[QR].Lrt, L, mid, pos);
    }
    if (pos >= mid + 1) {
        rk += query(tr[QL].Rrt, tr[QR].Rrt, mid + 1, R, pos);
    }
    return rk;
}
int rt[N];
array<int, 3> q[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    for (int i = 1 ; i <= m ; i++) {
        int L, R, k;
        cin >> L >> R >> k;
        q[i] = {L, R , k};
        idx.push_back(k);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    int len = idx.size() - 1;
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    for (int i = 1 ; i <= m ; i++) {
        q[i][2] = lower_bound(begin(idx), end(idx), q[i][2]) - begin(idx);
    }
    for (int i = 1 ; i <= n ; i++) {
        rt[i] = update(rt[i - 1], 1, len, a[i]);
    }
    for (int i = 1 ; i <= m ; i++) {
        auto [L, R, k] = q[i];
        cout << query(rt[L - 1], rt[R], 1, len, k) << "\n";
    }
    return 0;
}

静态区间[u,v]的个数

代码

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;
}();
const int N = 200005;
struct Node {
    int Lrt, Rrt;
    int sum;
} tr[N << 5];
int tot;
int a[N];
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 <= 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[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        rt[i] = update(rt[i - 1], 1, n, a[i]);
    }
    for (int i = 1 ; i <= m ; i++) {
        int L, R, VL, VR;
        cin >> L >> R >> VL >> VR;
        cout << query(rt[L - 1], rt[R], 1, n, VL, VR) << "\n";
    }
    return 0;
}

静态区间颜色数

例题

P1972 [SDOI2009] HH的项链 - 洛谷

代码

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;
}();
const int N = 1000005;
struct Node {
    int Lrt, Rrt;
    int sum;
} tr[N << 5];
int tot;
int a[N];
int update(int old, int L, int R, int pos, int k) {
    int now = ++tot;
    tr[now] = tr[old];
    tr[now].sum += k;
    if (L == R) {
        return now;
    }
    int mid = L + R >> 1;
    if (pos <= mid) {
        tr[now].Lrt = update(tr[now].Lrt, L, mid, pos, k);
    } else {
        tr[now].Rrt = update(tr[now].Rrt, mid + 1, R, pos, k);
    }
    return now;
}
int query(int rt, int L, int R, int pos) {
    if (L == R) {
        return tr[rt].sum;
    }
    int mid = L + R >> 1;
    if (pos <= mid) {
        return query(tr[rt].Lrt, L, mid, pos) + tr[tr[rt].Rrt].sum;
    }
    if (pos >= mid + 1) {
        return query(tr[rt].Rrt, mid + 1, R, pos);
    }
}
int rt[N];
int last[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        int temp = rt[i - 1];
        if (last[a[i]] != 0) {
            temp = update(rt[i - 1], 1, n, last[a[i]], -1);
        }
        rt[i] = update(temp, 1, n, i, 1);
        last[a[i]] = i;
    }
    int m;
    cin >> m;
    for (int i = 1 ; i <= m ; i++) {
        int L, R;
        cin >> L >> R;
        cout << query(rt[R], 1, n, L) << "\n";
    }
    return 0;
}