build： 这份代码有以下问题，在离散化得时候并没有按照离散化之后的vector大小进行查找（好像以修正）
-------------------------------------------------
题意：想学主席树，你就肯定知道这道题，去买个面包就有10个人会做的区间第k大（你懂得）
思路：主席树，听说好像其他的也可以做
下面大概说一下主席树，主席树可以进行离线的区间第k大，好像在线的是用树状数组套主席树（不对请大牛们留言指出），对于主席树的建树，很少有博客描述主席树的建树（可能我看的太少了），大家都是说一些，前缀和操作，很少说这个线段树到底维护的是什么东西，后来看了一篇博客的图（传送门 http://www.cnblogs.com/Empress/p/4652449.html），我才发现，是类似于权值线段树的，现在窝只是对于主席树有一点了解，其他的内容等待二更。
然后附上我抄袭的主席树代码：（话说里面的去重操作真的帅，村里人没见过）
之前代码有误，二更---
三更---修改为从0开始的主席树
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #define zero(a) fabs(a)<eps #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) #define lowbit(x) (x&(-x)) #define debug(a) cerr<<#a<<"=="<<a<<endl typedef long long LL; const double pi=acos(-1.0); const double eps=1e-8; const int inf=0x3f3f3f3f; const LL linf=0x3f3f3f3f3f3f3f3f; using namespace std; const int maxn=100000+7; int n,m,a[maxn],root[maxn],cnt,x,y,k; struct node { int l,r,sum; }T[maxn*40]; vector<int>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 ",query(0,v.size()-1,root[x-1],root[y],k)); printf("%d ",v[query(0,v.size()-1,root[x-1],root[y],k)]); } return 0; }