题意：
给长度为n的数组和m个区间，求这m个区间中第k小的数。
分析：
数组静态，区间和k动态，划分树的定义题，上模板。
代码：
//poj 2761
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
#define MID(a,b) (a+((b-a)>>1))
const int maxN=100010;
struct Node
{int val[maxN],num[maxN];
};struct Partition_tree
{int n,order[maxN];Node t[20];void init(int len){n=len;for(int i=1;i<=n;++i){scanf("%d",&order[i]);t[0].val[i]=order[i];}sort(order+1,order+1+n);build(1,n,0); } void build(int l,int r,int k){if(l==r) return;int mid=MID(l,r); int lsame=mid-l+1,same=0,ln=l,rn=mid+1;for(int i=l;i<=r;++i)if(t[k].val[i]<order[mid]) --lsame;for(int i=l;i<=r;++i){if(i==l) t[k].num[i]=0;else t[k].num[i]+=t[k].num[i-1]; if(t[k].val[i]<order[mid])t[k].num[i]++,t[k+1].val[ln++]=t[k].val[i];else if(t[k].val[i]>order[mid])t[k+1].val[rn++]=t[k].val[i];else{same++;if(same<=lsame)t[k].num[i]++,t[k+1].val[ln++]=t[k].val[i];else t[k+1].val[rn++]=t[k].val[i];}}build(l,mid,k+1);build(mid+1,r,k+1);}int query(int st,int ed,int x,int l,int r,int k){if(l==r) return t[k].val[l];int lx,ly,rx,ry,mid=MID(l,r);if(st==l) lx=0,ly=t[k].num[ed];else lx=t[k].num[st-1],ly=t[k].num[ed]-t[k].num[st-1];if(ly>=x){st=l+lx;ed=l+lx+ly-1;return query(st,ed,x,l,mid,k+1);}else{rx=st-1-l+1-lx;ry=ed-st+1-ly;st=mid+1+rx;ed=mid+1+rx+ry-1; return query(st,ed,x-ly,mid+1,r,k+1); }}
}tree;int main()
{int n,m;while(scanf("%d%d",&n,&m)==2){tree.init(n);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);printf("%d\n",tree.query(a,b,c,1,n,0));} } return 0;
}