poj2104主席树

题意

给定一个数列，给出若干个询问（l,r,k）,求出[l,r]区间内第k小的数。

做法

用若干棵线段树分别维护前缀Si的离散化后的该数的个数，即在某棵线段树中，第i个位置表示离散化后大小为i的元素的个数，查询时在线段树上进行二分。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
class node{
public:
    int l,r, sum;
    node  *linkl, *linkr;
};
const int nn=100005;
node* root[nn];
class node1{
public:
    int x, num;
} a1[nn];
int a[nn];
int num;
int hash[nn];
int n,m;
void build(node *&p, int l, int r){
    p=(node*)malloc(sizeof(node));
    p->l = l; p->r = r; p->linkl = p->linkr = NULL;
    if (l < r){
        int mid = (l + r) >> 1;
        build(p->linkl, l, mid);
        build(p->linkr, mid+1, r);
        p->sum = p->linkl->sum + p->linkr->sum;
    } else{
        p->sum = 0;
    }
}
void build1(int x, node *&p, node *p1, int l,int r){
    p=(node*)malloc(sizeof(node));
 
    p->l = l; p->r = r;
    p->linkl = p->linkr = NULL;
    if (l < r) {
        int mid = (l + r) >> 1;
        if (x <= mid){
            build1(x, p->linkl, p1->linkl, l, mid);
            p->linkr = p1->linkr;
        } else {
            build1(x, p->linkr, p1->linkr, mid+1, r);
            p->linkl = p1->linkl;
        }
        p->sum = p->linkl->sum + p->linkr->sum;
    } else p->sum = p1->sum + 1;
}
inline int check(node *p1, node *p2, int k){
    while (p1->l != p1->r){
        if (k <= p2->linkl->sum - p1->linkl->sum) {
            p2 = p2 -> linkl; p1 = p1 -> linkl;
        } else{
            k -= (p2 -> linkl->sum - p1->linkl->sum);
            p2 = p2 -> linkr; p1 = p1 ->linkr;
        }
    }
    return (p1->l);
}
int scan(){
    char c;
    int x(0);
    bool f(false);
    while(c=getchar(),c==' ' || c== '\n');
    if (c == '-') {
        f = true;
        c = getchar();
    }
    x=c-'0';
    while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
    if (f) x = 0 - x;
    return x;
}
void qsort(int l, int r){
    node1 mid=a1[(l + r) >> 1];
    int i(l), j(r);
    node1 t;
    do{
        while (a1[i].x < mid.x) ++i;
        while (a1[j].x > mid.x) --j;
        if (i <= j){
            t = a1[i]; a1[i] = a1[j]; a1[j] = t;
            ++i; --j;
        }
    } while (i < j);
    if (l < j) qsort(l, j);
    if (i < r) qsort(i, r);
}
int main(){
    freopen("poj2104.in", "r", stdin);
    freopen("poj2104.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=1;i<=n;++i){
        a1[i].x = scan();
        a1[i].num = i;
    }
    qsort(1, n);
    a[a1[1].num] = 1;
    hash[1] = a1[1].x;
    num = 1;
    for (int i=2;i<=n;++i){
        if (a1[i].num != a1[i-1].num) ++num;
        a[a1[i].num] = num;
        hash[num] = a1[i].x;
    }
    build(root[0], 1, num);
    for (int i=1;i<=num;++i) build1(a[i], root[i], root[i-1], 1, num);
    int l,r,k;
    for (int i=1;i<=m;++i){
        l = scan(); r = scan(); k = scan();
        printf("%d\n", hash[check(root[l-1], root[r], k)]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}