所谓主席树，就是求区间第$k$大。

最普通的想法，对每个区间$[1,i]$都建立一棵线段树，可行是可行的，但是空间复杂度达到了惊人的$O(n^2)$，对于数据结构来说，是不可以忍受的。

那么我们伟大的$fotile$主席就$yy$出来了$ChairTree$这玩意，也就是主席树。

其实主席树就是有n棵权值线段树，注意到每次仅在前面的基础上改变$log_n$个点，那么我们只需要对这$log_n$个点重新提出来建即可。

权值线段树就是把数据离散后存入线段树，每个节点表示值为当前这个节点的编号(离散后$[1,n]$)的有多少个。

时间和空间的复杂度都为$O(nlog_n)$。

然后我们就来看看POJ 2104:传送门

这题就是一模一样的主席树啦，打打当模板用。

# include <stdio.h>
# include <algorithm>
using namespace std;
const int Maxn=100010;
struct segtree {
	int l,r,w;
	segtree() {l=r=w=0;}
}T[21*Maxn];
# define lc(a) T[(a)].l
# define rc(a) T[(a)].r
# define w(a) T[(a)].w
int bf[Maxn];
int a[Maxn],root[Maxn],b[Maxn],p[Maxn];
int n,m;
int size;
inline int cmp(int _a,int _b) {return a[_a]<a[_b];}
void insert(int &roots,int l,int r,int x) {
	T[++size]=T[roots]; roots=size;
	w(roots)++;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) insert(lc(roots),l,mid,x);
	else insert(rc(roots),mid+1,r,x); 
}
int query(int i,int j,int l,int r,int k) {
	if(l==r) return l;
	int t=w(lc(j))-w(lc(i));
	int mid=(l+r)>>1;
	if(t>=k) return query(lc(i),lc(j),l,mid,k);
	else return query(rc(i),rc(j),mid+1,r,k-t);
}
int main() {
	while(scanf("%d%d",&n,&m)!=EOF) {
		size=0;root[0]=0;
		for (int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
			p[i]=i;
		}
		sort(p+1,p+n+1,cmp);
		for (int i=1;i<=n;++i) b[p[i]]=i;
		for (int i=1;i<=n;++i) {
			root[i]=root[i-1];
			insert(root[i],1,n,b[i]);
		}
		for (int i=1;i<=m;++i) {
			int x,y,k; scanf("%d%d%d",&x,&y,&k);
			int t=query(root[x-1],root[y],1,n,k);
			printf("%d\n",a[p[t]]);
		}
	}
}