POJ 2104 主席树模板题

#include <iostream>
#include <cstdio>
#include <algorithm>
int const maxn = 200010;
using namespace std;
int a[maxn],b[maxn];
//第几个版本的根节点编号
int root[maxn << 5];
int lc[maxn << 5],rc[maxn << 5],sum[maxn << 5];
int sz;//节点个数
int n,m;
int true_n;


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

int update(int id,int r,int pos) {
    int _id = ++sz;
    lc[_id] = lc[id],rc[_id] = rc[id],sum[_id] = sum[id] + 1;
    if (l == r) return _id;
    int mid = (r + l) >> 1;
    if (pos <= mid)
        lc[_id] = update(lc[id],mid,pos);
    else
        rc[_id] = update(rc[id],r,pos);
    return _id;
}

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


int main() {
    while (~scanf("%d %d",&n,&m)) {
        sz = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        sort(b + 1,b + n + 1);
        true_n = unique(b + 1,b + n + 1) - b - 1;
        build(root[0],1,true_n);
        for (int i = 1; i <= n; i++) {
            int pos = lower_bound(b + 1,b + true_n + 1,a[i]) - b;
            root[i] = update(root[i - 1],true_n,pos);
        }
        while (m--) {
            int l,k;
            scanf("%d %d %d",&l,&r,&k);
            cout << b[query(root[l - 1],root[r],k)] << endl;
        }
    }
    return 0;
}