题目背景
这是个非常经典的主席树入门题——静态区间第K小
数据已经过加强，请使用主席树。同时请注意常数优化
题目描述
如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。
输入输出格式
输入格式：
第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。
第二行包含N个正整数，表示这个序列各项的数字。
接下来M行每行包含三个整数l,r,k l, r, kl,r,k , 表示查询区间[l,r][l, r][l,r]内的第k小值。
输出格式：
输出包含k行，每行1个正整数，依次表示每一次查询的结果
输入输出样例
输入样例#1：
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
输出样例#1：
6405
15770
26287
25957
26287
说明
数据范围：
对于20%的数据满足：1≤N,M≤10
对于50%的数据满足：1≤N,M≤1033
对于80%的数据满足：1≤N,M≤1055
对于100%的数据满足：1≤N,M≤2⋅1055
对于数列中的所有数aii，均满足−109≤ai≤109-{10}^9 \leq a_i \leq {10}^9−109≤ai≤109
样例数据说明：
N=5，数列长度为5，数列从第一项开始依次为25957,6405,15770,26287,26465
第一次查询为[2,2]区间内的第一小值，即为6405
第二次查询为[3,4]区间内的第一小值，即为15770
第三次查询为[4,5]区间内的第一小值，即为26287
第四次查询为[1,2]]区间内的第二小值，即为25957
第五次查询为[4,4]区间内的第一小值，即为26287
主席树真奇妙
给出两位巨佬的链接
第一个很详细的解释了主席树
第二个给出了此题的所有做法
http://www.cnblogs.com/zyf0163/p/4749042.html
http://www.cnblogs.com/NaVi-Awson/p/7325571.html
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct Node
{
int key;
Node *ch[];
}S[N*],*pos=S;
Node *root[N+];
int a[N+],b[N+],n,m,sz,rem[N+];
void build(Node* &rt,int l,int r)
{
rt=++pos;
rt->key=;
if (l==r) return;
int mid=(l+r)/;
build(rt->ch[],l,mid);
build(rt->ch[],mid+,r);
}
void insert(Node* &rt,int l,int r,int k)
{
Node *x=rt;
rt=++pos;
rt->ch[]=x->ch[];
rt->ch[]=x->ch[];
rt->key=x->key+;
if (l==r) return;
int mid=(l+r)/;
if (k<=mid) insert(rt->ch[],l,mid,k);
else insert(rt->ch[],mid+,r,k);
}
int query(Node* rl,Node* rr,int l,int r,int k)
{
if (l==r) return l;
int mid=(l+r)/;
int x=rr->ch[]->key-rl->ch[]->key;
if (x>=k) return query(rl->ch[],rr->ch[],l,mid,k);
else return query(rl->ch[],rr->ch[],mid+,r,k-x);
}
int main()
{int i,j,x,y,k;
cin>>n>>m;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+,b+n+);
sz=unique(b+,b+n+)-(b+);
for (i=;i<=n;i++)
a[i]=lower_bound(b+,b+sz+,a[i])-b;
build(root[],,n);
for (i=;i<=n;i++)
{
root[i]=root[i-];
insert(root[i],,n,a[i]);
}
while (m--)
{
scanf("%d%d%d",&x,&y,&k);
int ans=query(root[x-],root[y],,n,k);
printf("%d\n",b[ans]);
}
}
