[Luogu] 可持久化线段树 1（主席树）

https://www.luogu.org/problemnew/show/P3834

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 2e5 + ;

#define RR freopen("gg.in", "r", stdin)

int n, m;

int cnt;

struct node {

    int L, R;//分别指向左右子树

    int sum;//该节点对应区间数的个数

    node() {

        sum = ;

    }

} Tree[maxn * ];

struct value {

    int x;//值的大小

    int id;//离散之前在原数组中的位置

} Value[maxn];

bool cmp(value v1, value v2) {

    return v1.x < v2.x;

}

int root[maxn];//多颗线段树的根节点

int rank[maxn];//原数组离散之后的数组

void init() {

    cnt = ;

    root[] = ;

    Tree[].L = Tree[].R = Tree[].sum = ;

}

void update(int num, int &rt, int l, int r) {

    Tree[cnt++] = Tree[rt];//bu存在Tree[0]

    rt = cnt - ;

    Tree[rt].sum++;

    if(l == r) return;

    int mid = (l + r)>>;

    if(num <= mid) update(num, Tree[rt].L, l, mid);

    else update(num, Tree[rt].R, mid + , r);

}

int query(int i, int j, int k, int l, int r) {

    int d = Tree[Tree[j].L].sum - Tree[Tree[i].L].sum;

    if(l == r) return l;

    int mid = (l + r)>>;

    if(k <= d) return query(Tree[i].L, Tree[j].L, k, l, mid);

    else return query(Tree[i].R, Tree[j].R, k - d, mid + , r);

}

int main() {

    RR;

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; i++) {

        scanf("%d", &Value[i].x);

        Value[i].id = i;

    }

    //进行离散化

    sort(Value + , Value + n + , cmp);

    for(int i = ; i <= n; i++) rank[Value[i].id] = i;

    init();

    for(int i = ; i <= n; i++) {

        root[i] = root[i - ];

    //    cout << root[i] << endl;

        update(rank[i], root[i], , n);//update(第i个数的排名，)

    }

    int left, right, k;

    for(int i = ; i <= m; i++) {

        scanf("%d%d%d", &left, &right, &k);

        printf("%d\n", Value[query(root[left - ], root[right], k, , n)].x);

    }

    return ;

}