[模板]主席树

求区间第K小：

#include
#include
#include<string>
#include
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct ChairMan{
    int lson,rson,val;//记录左儿子右儿子，还有一个大小
    ChairMan(){val=0;}//为了节约空间最好别用l,r
    //毕竟有丧心病狂的O(nlogn)空间……
}tree[WR<<4];//空间开大
int n,m,un;
int a[WR],b[WR];
int root[WR],tot;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void pushup(int k){//这里相应的要改一下
    tree[k].val=tree[tree[k].lson].val+tree[tree[k].rson].val;
}
void cpy(int x,int y){
    tree[x].lson=tree[y].lson,tree[x].rson=tree[y].rson;
    tree[x].val=tree[y].val;
}
void build(int &k,int l,int r){//动态开点建树
    if(!k) k=++tot;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(tree[k].lson,l,mid);
    build(tree[k].rson,mid+1,r);
}
void insrt(int &k,int l,int r,int pos,int v){
    if(!k) k=++tot;
    cpy(k,pos);
    if(l==r){
        tree[k].val++;
        return;
    }
    int mid=(l+r)>>1;//权值线段树式的修改
    if(v<=mid) tree[k].lson=0,insrt(tree[k].lson,l,mid,tree[pos].lson,v);
    else tree[k].rson=0,insrt(tree[k].rson,mid+1,r,tree[pos].rson,v);
    pushup(k);
}
int query(int k,int l,int r,int pos,int v){
    if(l==r) return l;
    int tmp=tree[tree[k].lson].val-tree[tree[pos].lson].val;
    int mid=(l+r)>>1;
    if(v<=tmp) return query(tree[k].lson,l,mid,tree[pos].lson,v);
    else return query(tree[k].rson,mid+1,r,tree[pos].rson,v-tmp);
    //这里有一点点小差分，如果当前第k大在左子树里，直接查左子树
    //如果在右子树里，剪掉左子树大小再查询
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=b[i]=read();
    sort(b+1,b+1+n);
    un=unique(b+1,b+1+n)-b-1;//必备离散化
    build(root[0],1,un);//先建出权值线段树再说插入的事
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+un+1,a[i])-b;
        //printf("a[i]=%d\n",a[i]);
        insrt(root[i],1,un,root[i-1],a[i]);
    }
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),k=read();
        printf("%d\n",b[query(root[y],1,un,root[x-1],k)]);
    }
    return 0;
}