本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
Input
Output
Sample Input
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1
Sample Output
3 2
正解：主席树
解题报告：
主席树裸题，维护区间第k大数查询。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 100011;
int n,m,a[MAXN],c[MAXN],L,cnt,root[MAXN];
struct node{ int ls,rs,val; }tr[MAXN*20];
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline int build(int rt,int l,int r,int k){
cnt++; tr[cnt]=tr[rt]; tr[cnt].val++; if(l==r) return cnt;
int cc=cnt; int mid=(l+r)>>1;
if(k<=mid) tr[cc].ls=build(tr[rt].ls,l,mid,k);
else tr[cc].rs=build(tr[rt].rs,mid+1,r,k);
return cc;
}
inline int query(int up,int down,int l,int r,int k){
if(l==r) return l; int cp=tr[ tr[up].ls ].val-tr[ tr[down].ls ].val; int mid=(l+r)>>1;
if(k<=cp) return query(tr[up].ls,tr[down].ls,l,mid,k);
else return query(tr[up].rs,tr[down].rs,mid+1,r,k-cp);
}
inline void work(){
n=getint(); m=getint(); for(int i=1;i<=n;i++) a[i]=getint(),c[i]=a[i];
sort(c+1,c+n+1); L=unique(c+1,c+n+1)-c-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+L+1,a[i])-c;
for(int i=1;i<=n;i++) root[i]=build(root[i-1],1,L,a[i]);
int l,r,k;
while(m--) {
l=getint(); r=getint(); k=getint();
printf("%d\n",c[ query(root[r],root[l-1],1,L,k) ]);
}
}
int main()
{
work();
return 0;
}
原文：http://www.cnblogs.com/ljh2000-jump/p/6279097.html