build： 这份代码有以下问题，在离散化得时候并没有按照离散化之后的vector大小进行查找（好像以修正）
-------------------------------------------------
题意：想学主席树，你就肯定知道这道题，去买个面包就有10个人会做的区间第k大（你懂得）
思路：主席树，听说好像其他的也可以做
下面大概说一下主席树，主席树可以进行离线的区间第k大，好像在线的是用树状数组套主席树（不对请大牛们留言指出），对于主席树的建树，很少有博客描述主席树的建树（可能我看的太少了），大家都是说一些，前缀和操作，很少说这个线段树到底维护的是什么东西，后来看了一篇博客的图（传送门 http://www.cnblogs.com/Empress/p/4652449.html），我才发现，是类似于权值线段树的，现在窝只是对于主席树有一点了解，其他的内容等待二更。
然后附上我抄袭的主席树代码：（话说里面的去重操作真的帅，村里人没见过）
之前代码有误，二更---
三更---修改为从0开始的主席树
#include #include
v;int getid(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin();}void update(int l,int r,int &x,int y,int pos){ T[++cnt]=T[y],T[cnt].sum++,x=cnt; if(l==r)return ; int mid=(l+r)>>1; if(pos<=mid)update(l,mid,T[x].l,T[y].l,pos); else update(mid+1,r,T[x].r,T[y].r,pos);}int query(int l,int r,int x,int y,int k){ if(l==r)return l; int mid=(l+r)>>1; int now=T[T[y].l].sum-T[T[x].l].sum; if(k<=now)query(l,mid,T[x].l,T[y].l,k); else query(mid+1,r,T[x].r,T[y].r,k-now);}int main(){ memset(root,0,sizeof(root)); cnt=0; v.clear(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++){ update(0,v.size()-1,root[i],root[i-1],getid(a[i])); } while(m--){ scanf("%d%d%d",&x,&y,&k);// printf("test %d\n",query(0,v.size()-1,root[x-1],root[y],k)); printf("%d\n",v[query(0,v.size()-1,root[x-1],root[y],k)]); } return 0;}