我的第一道主席树（静态）。
先记下自己对主席树的理解：
主席树的作用是用于查询区间第k大的元素（初始化nlog(n)，查询log(n)）
主席树=可持续线段树+前缀和思想
主席树实际上是n棵线段树（由于是可持续化线段树，所以实际上是n个长度为log(n)的链），第i棵线段树保存的是a[1]~a[i]这i个数的值域线段树，每个节点维护的是该值域中元素个数，这个是可以相减的，所以建完树后，查询[lf,rg]的第k大时，保存当前查询的值域区间在lf-1和rg这两棵线段树中的节点u,v（不理解看代码），再向下查找时，根据
size[v]-size[u]与k（这里的k是在当前值域的第k大）的大小关系决定向值域的左走还是右走。
（注意空间！）
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define maxs 18*maxn
using namespace std; struct SegTree {
int son[maxs][], siz[maxs], ntot;
int root[maxn], vmin, vmax; int modify( int v, int nd, int lf, int rg ) {
if( lf>=rg ) return ;
int newd = ++ntot;
if( lf+==rg ) {
siz[newd] = siz[nd]+;
son[newd][] = son[newd][] = ;
return newd;
}
int mid = (lf+rg)>>;
if( v<mid ) {
son[newd][] = modify( v, son[nd][], lf, mid );
son[newd][] = son[nd][];
} else {
son[newd][] = son[nd][];
son[newd][] = modify( v, son[nd][], mid, rg );
}
siz[newd] = siz[son[newd][]]+siz[son[newd][]];
return newd;
}
int query( int k, int u, int v, int lf, int rg ) {
int ls = siz[son[v][]]-siz[son[u][]];
if( lf+==rg ) return lf;
int mid = (lf+rg)>>;
if( k<=ls ) return query(k,son[u][],son[v][],lf,mid);
else return query(k-ls,son[u][],son[v][],mid,rg);
} void init( int n ) {
ntot = ;
vmin = ;
vmax = n+;
root[] = ;
}
void modify( int pos, int val ) {
root[pos] = modify( val, root[pos-], vmin, vmax );
}
int query( int k, int lf, int rg ) {
return query( k, root[lf-], root[rg], vmin, vmax );
}
}; int n, m;
SegTree T;
int a[maxn];
int sval[maxn], tot; int main() {
scanf( "%d%d", &n, &m );
T.init(n);
for( int i=; i<=n; i++ ) {
scanf( "%d", a+i );
sval[i] = a[i];
}
sort( sval+, sval++n );
tot = unique( sval+, sval++n ) - sval;
for( int i=; i<=n; i++ ) {
int dv = lower_bound(sval+,sval++tot,a[i])-sval;
T.modify( i, dv );
}
for( int i=,k,lf,rg; i<=m; i++ ) {
scanf( "%d%d%d", &lf, &rg, &k );
printf( "%d\n", sval[T.query(k,lf,rg)] );
}
}