poj2104-基础主席树

//因为保证了树的相同所以可以线段树树加减从而求出欲求区域

#include<stdio.h>  
#include<stdlib.h>  
#include<algorithm>  
using namespace std;  
const int oo=2000000010;  
int s,ans,a[100010],b[100010],begin[100010];  
struct node{  
    int l,r,s;  
}tree[2000010];  
int home(int l,int r){  
    int d=++s;  
    if(l==r)  
        return d;  
    int mid=(l+r)>>1;  
    tree[d].l=home(l,mid);  
    tree[d].r=home(mid+1,r);  
    return d;  
}  
int build(int i,int k,int l,int r){  
    int d=++s;  
    tree[d]=tree[i];  
    tree[d].s+=1;  
    if(l==r)  
        return d;  
    int mid=(l+r)>>1;  
    if(k<=mid)  
        tree[d].l=build(tree[i].l,k,l,mid);  
    else  
        tree[d].r=build(tree[i].r,k,mid+1,r);  
    return d;  
}  
int find(int l,int r,int i,int d,int &k){  
    if(tree[d].s-tree[i].s<k){  
        k-=tree[d].s-tree[i].s;  
        return 0;  
    }  
    if(tree[d].s-tree[i].s>=k && l==r){  
        printf("%d\n",b[l]);  
        return 1;  
    }  
    int mid=(l+r)>>1;  
    if(find(l,mid,tree[i].l,tree[d].l,k))return 1;  
    if(find(mid+1,r,tree[i].r,tree[d].r,k))return 1;  
    return 0;  
}  
int main(){  
    int i,k,l,r,n,m,sun;  
    scanf("%d%d",&n,&m);  
    for(i=1;i<=n;i++){  
        scanf("%d",&a[i]);  
        b[i]=a[i];  
    }  
    sort(b+1,b+1+n);  
    sun=unique(b+1,b+1+n)-b-1;//去重函数，将相邻的重复元素去掉，返回尾地址，因为它将重复的元素放到最后面了。  
    sun++;b[sun]=oo;  
    begin[0]=home(1,sun);  
    for(i=1;i<=n;i++){  
        k = lower_bound( b + 1, b + 1 + sun, a[i] ) - b;//返回大于或等于b的第一个元素的地址  
        begin[i]=build(begin[i-1],k,1,sun);  //begin[i]为第i个树的根 
    }  
    for(i=1;i<=m;i++){  
        scanf("%d%d%d",&l,&r,&k);  
        find(1,sun,begin[l-1],begin[r],k);  
    }  
    return 0;  
}