主席树

ACWing 墨染空  
https://www.acwing.com/blog/content/487/ 

基于主席树的可持久化数组！
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

typedef long long ll;
const int N = 1e6+9;
int a[N],root[N];
int tot;

struct SegmentTree {
    int ls,rs,v;
}tr[N << 5];

int build(int l,int r) {
    int p = ++tot,mid = l + r >> 1;
    if(l == r) {
        tr[p].v = a[l];
        return p;
    }
    tr[p].ls = build(l,mid);
    tr[p].rs = build(mid+1,r);
    return p;
}

int update(int p,int l,int r,int x,int val) {
    int q = ++tot;
    tr[q] = tr[p];
    if(l == r) {
        tr[q].v = val;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].ls = update(tr[q].ls,l,mid,x,val);
    else tr[q].rs = update(tr[q].rs,mid+1,r,x,val);
    return q;
}

int query(int q,int l,int r,int k) {
    if(l == r) {
        return tr[q].v;
    }
    int mid = l + r >> 1;
    if(k <= mid) return query(tr[q].ls,l,mid,k);
    else return query(tr[q].rs,mid+1,r,k);
}

int main() {
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    root[0] = build(1,n);
    for(int i=1; i<=m; i++) {
        int num,op;
        scanf("%d%d",&num,&op);
        if(op == 1) {
            int x,y;
            scanf("%d%d",&x,&y);
            root[i] = update(root[num],1,n,x,y);
        } else {
            int k;
            scanf("%d",&k);
            printf("%d\n",query(root[num],1,n,k));
            root[i] = root[num];
        }
    }
    return 0;
}

主席树 + 离散化
静态区间第k小！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 1e5+9;
int a[N],b[N],root[N],tot;

struct SegmentTree {
    int ls,rs,v;
}tr[N << 5];

void pushup(int u) {
    tr[u].v = tr[tr[u].ls].v + tr[tr[u].rs].v;
}

int build(int l,int r) {
    int p = ++tot,mid = l + r >> 1;
    if(l == r) return p;
    tr[p].ls = build(l,mid);
    tr[p].rs = build(mid+1,r);
    return p;
}

int insert(int p,int l,int r,int x) {
    int q = ++tot;
    tr[q] = tr[p];
    if(l == r) {
        tr[q].v++;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].ls = insert(tr[p].ls,l,mid,x);
    else tr[q].rs = insert(tr[p].rs,mid+1,r,x);
    pushup(q);
    return q;
}

int query(int q,int p,int l,int r,int k) {
    if(l == r) return l;
    int cnt = tr[tr[q].ls].v - tr[tr[p].ls].v;
    int mid = l + r >> 1;
    if(k <= cnt) return query(tr[q].ls,tr[p].ls,l,mid,k);
    else return query(tr[q].rs,tr[p].rs,mid+1,r,k - cnt);
}

int main() {
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]),b[i] = a[i];
    sort(b+1,b+n+1);
    int len = unique(b+1,b+n+1) - b - 1;
    root[0] = build(1,len);
    for(int i=1; i<=n; i++) {
        int p = lower_bound(b+1,b+len+1,a[i]) - b;
        root[i] = insert(root[i-1],1,len,p);
    }
    while(m--) {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",b[query(root[r],root[l-1],1,len,k)]);
    }
    return 0;
}

作者：我木jj我怕谁
链接：https://www.acwing.com/activity/content/code/content/4211910/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

主席树动态开点版本 //应该无？