题目链接：
http://poj.org/problem?id=2104
K-th Number
Time Limit: 20000MSMemory Limit: 65536K
#### 问题描述
> You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
> That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
> For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
#### 输入
> The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
> The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 For each question output the answer to it --- the k-th number in sorted a[i...j] segment.
####样例输入
> 7 3
> 1 5 2 6 3 7 4
> 2 5 3
> 4 4 1
> 1 7 3
####样例输出
> 5
> 6
> 3
## 题意
> 给你n个数m个询问，每个询问给你l,r,k，求（l,r）区间里第k大的数，保证每个数只出现一次。
题解
代码
本土化：
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson(i) (tre[(i)].ls)
#define rson(i) (tre[(i)].rs)
#define sumv(i) tre[(i)].sum
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=1e5+10;
///nlogn空间复杂度
struct Tre{
int ls,rs,sum;
Tre(){ls=rs=sum=0;}
}tre[maxn*20];
int n,m;
int rt[maxn],tot;
int _v;
void update(int &o,int l,int r){
tre[++tot]=tre[o],o=tot;
if(l==r){
sumv(o)++;
}else{
if(_v<=mid) update(lson(o),l,mid);
else update(rson(o),mid+1,r);
sumv(o)=sumv(lson(o))+sumv(rson(o));
}
}
int _res;
void query(int o1,int o2,int l,int r,int k){
if(l==r){
_res=l;
}else{
///前缀和思想
int cnt=sumv(lson(o2))-sumv(lson(o1));
if(cnt>=k) query(lson(o1),lson(o2),l,mid,k);
else query(rson(o1),rson(o2),mid+1,r,k-cnt);
}
}
int idx[maxn],arr[maxn],ra[maxn];
bool cmp(int x,int y){
return arr[x]<arr[y];
}
///0是个超级节点
void init(){
rt[0]=tot=0;
}
int main() {
while(scf("%d%d",&n,&m)==2&&n){
init();
for(int i=1;i<=n;i++) scf("%d",&arr[i]);
for(int i=1;i<=n;i++) idx[i]=i;
///离散化
sort(idx+1,idx+n+1,cmp);
for(int i=1;i<=n;i++) ra[idx[i]]=i;
///主席树
for(int i=1;i<=n;i++){
_v=ra[i];
rt[i]=rt[i-1];
update(rt[i],1,n);
}
///查询区间第k大
while(m--){
int l,r,k;
scf("%d%d%d",&l,&r,&k);
query(rt[l-1],rt[r],1,n,k);
prf("%d\n",arr[idx[_res]]);
}
}
return 0;
}
//end-----------------------------------------------------------------------