主席树板子

写点常用板子，随时可以用。
题目是k-th number
poj2104

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100010;
const int N=maxn*40;
int n,m,q,tot=0;
int T[maxn],A[maxn],B[maxn];
struct node{
   
	int sum,lson,rson;
}tree[N];
int getid(int x){
   
	return lower_bound(B+1,B+m+1,x)-B;
}
int build(int l,int r){
   
	int p=++tot;
	tree[p].sum=0;
	if(l!=r){
   
		int mid=(l+r)>>1;
		tree[p].lson=build(l,mid);
		tree[p].rson=build(mid+1,r);
	}
	return p;
}
int update(int now,int x,int l,int r){
   
	int p=++tot;
	tree[p].sum=tree[now].sum;
	tree[p].lson=tree[now].lson;
	tree[p].rson=tree[now].rson;
	if(l==r){
   
		tree[p].sum++;
		return p;
	}
	int mid=(l+r)>>1;
	if(x<=mid)	tree[p].lson=update(tree[now].lson,x,l,mid);
	else tree[p].rson=update(tree[now].rson,x,mid+1,r);
	tree[p].sum=tree[tree[p].lson].sum+tree[tree[p].rson].sum;
	return p;	
}
int ask(int p,int q,int l,int r,int k){
   
	if(l==r)	return l;
	int mid=(l+r)>>1;
	int lcnt=tree[tree[p].lson].sum-tree[tree[q].lson].sum;
	if(k<=lcnt)	return ask(tree[p].lson,tree[q].lson,l,mid,k);
	else return	ask(tree[p].rson,tree[q].rson,mid+1,r,k-lcnt);
}
int main(){
   
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
   
		scanf("%d",&A[i]);
		B[i]=A[i];
	}
	sort(B+1,B+n+1);
	m=unique(B+1,B+n+1)-B-1;

	T[0]=build(1,m);
	for(int i=1;i<=m;i++)
		T[i]=update(T[i-1],getid(A[i]),1,m);
	while(q--){
   
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		printf("%d\n",B[ask(T[y],T[x-1],1,m,k)]);
	}
	return 0;
}