洛谷--主席樹模闆

一、P3919 【模闆】可持久化線段樹 1（可持久化數組）

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

const int N = 1e6 + 10;

int root[N], n, m;
int lc[N << 5], rc[N << 5], sum[N << 5], tot;

void build(int &rt, int l, int r){
    rt = ++tot;
    if(l == r){
        cin >> sum[rt];
        return;
    }
    int mid = l + r >> 1;
    build(lc[rt], l, mid);
    build(rc[rt], mid + 1, r);
}

void update(int &rt, int pre, int l, int r, int x, int v){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre];
    if(l == r){
        sum[rt] = v;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid) update(lc[rt], lc[pre], l, mid, x, v);
    else update(rc[rt], rc[rt], mid + 1, r, x, v);
}

int query(int &rt, int l, int r, int x){
    if(l == r) return sum[rt];
    int mid = l + r >> 1;
    if(x <= mid) return query(lc[rt], l, mid, x);
    else return query(rc[rt], mid + 1, r, x);
}



signed main(){
       //freopen("stdin.in", "r", stdin);
       //freopen("stdout.out", "w", stdout);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    build(root[0], 1, n);
    for(int i = 1; i <= m; i++){
        int pre, op, v, x;
        cin >> pre >> op >> x;
        if(op == 1){
            cin >> v;
            update(root[i], root[pre], 1, n, x, v);
        }
        else{
            cout << query(root[pre], 1, n, x) << endl;
            root[i] = root[pre];
        }
    }


    return 0;
}      

二、P3834 【模闆】可持久化線段樹 2（主席樹）

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

const int N = 2e5 + 10;

int a[N], b[N], n, m;
int root[N], tot;
int lc[N << 5], rc[N << 5], sum[N << 5];

void update(int &rt, int pre, int l, int r, int x, int v){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) update(lc[rt], lc[pre], l, mid, x, v);
    else update(rc[rt], rc[pre], mid + 1, r, x, v);
}

int query(int L, int R, int l, int r, int k){
    if(l == r) return l;
    int summ = sum[lc[R]] - sum[lc[L]], mid = l + r >> 1;
    if(summ >= k) return query(lc[L], lc[R], l, mid, k);
    else return query(rc[L], rc[R], mid + 1, r, k - summ);
}


signed main(){
       //freopen("stdin.in", "r", stdin);
       //freopen("stdout.out", "w", stdout);
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int n_1 = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i <= n; i++){
        update(root[i], root[i - 1], 1, n_1, lower_bound(b + 1, b + 1 + n_1, a[i]) - b, 1);
    }
    for(int i = 1; i <= m; i++){
        int l, r, k; cin >> l >> r >> k;
        cout << b[query(root[l - 1], root[r], 1, n_1, k)] << endl;
    }
    //for(int i = 1; i <= n; i++) cout << sum[i] << endl;
    return 0;
}