传送门：http://poj.org/problem?id=2104
题目大意：给定一个长度为N的数组{A[i]}，你的任务是解决Q个询问。每次询问在A[l], A[l+1], ...... , A[r]的子区间（
下标从1开始）内，第K大的数是多少。这里的第K大数可以理解为，将给定子数组拿出来按升序排序，其中排在第K
个的数。注意询问操作并不更改原数组。
题解：水题，主席树回顾-----------
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define maxn 100005
using namespace std;
int a[maxn],list[maxn];
int root[maxn],ls[maxn*],rs[maxn*],sum[maxn*];
int n,m,sz;
int read()
{
int x=; char ch; bool bo=;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') bo=;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
if (bo) return -x; return x;
}
void ins(int l,int r,int x,int &y,int val)
{
y=++sz; sum[y]=sum[x]+;
if (l==r) return;
ls[y]=ls[x]; rs[y]=rs[x];
int mid=(l+r)>>;
if (val<=mid) ins(l,mid,ls[x],ls[y],val);
else ins(mid+,r,rs[x],rs[y],val);
}
void init()
{
n=read(); m=read();
for (int i=; i<=n; i++) list[i]=a[i]=read();
sort(list+,list++n);
for (int i=; i<=n; i++) a[i]=lower_bound(list+,list++n,a[i])-list;
for (int i=; i<=n; i++) ins(,n,root[i-],root[i],a[i]);
}
int query(int L,int R,int k)
{
int l=,r=n,x=root[L-],y=root[R];
while (l!=r)
{
int tmp=sum[ls[y]]-sum[ls[x]];
int mid=(l+r)>>;
if (k<=tmp)
{
r=mid,x=ls[x],y=ls[y];
}
else
{
l=mid+,k-=tmp,x=rs[x],y=rs[y];
}
}
return l;
}
void solve()
{
for (int i=; i<=m; i++)
{
int l=read(),r=read(),k=read();
int ans=query(l,r,k);
printf("%d\n",list[ans]);
}
}
int main()
{
init();
solve();
}