Problem Description Give you a sequence and ask you the kth big number of a inteva l.
Input The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
Output For each test case, output m lines. Each line contains the kth big number.
Sample Input
1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2
Sample Output
2
Source HDU男生专场公开赛――赶在女生之前先过节（From WHU）
思路：划分树板子题。
#include
#include
using namespace std; int n,num[100005],sorted[100005],node[20][100005],sum[20][100005]; void build(int c,int s,int e)//第c层，s到e { int mid,lm,lp,rp,i; mid=(s+e)>>1; lm=0; lp=s;//左子树的头指针 rp=mid+1;//右子树的头指针 for(i=s;i<=mid;i++) if(sorted[i]==sorted[mid]) lm++;//求出s到e有多少个数等于sorted[mid] for(i=s;i<=e;i++) { if(i==s) sum[c][i]=0;//计算出s到i之间有多少个被分到了左子树 else sum[c][i]=sum[c][i-1]; if(node[c][i]==sorted[mid]) { if(lm) { lm--; sum[c][i]++; node[c+1][lp++]=node[c][i]; } else node[c+1][rp++]=node[c][i]; } else if(node[c][i]
>1; if(s==l)//特判 { ls=0; rs=sum[c][r]; } else { ls=sum[c][l-1]; rs=sum[c][r]-ls; } if(rs>=k) return query(c+1,s,mid,s+ls,s+ls+rs-1,k);//要查询的数在左子树 else return query(c+1,mid+1,e,mid-s+1+l-ls,mid-s+1+r-ls-rs,k-rs);//要查询的数在右子树 } } int main() { int T,m,i,a,b,k; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&num[i]); node[0][i]=sorted[i]=num[i]; } sort(sorted+1,sorted+n+1); build(0,1,n); while(m--) { scanf("%d%d%d",&a,&b,&k); printf("%d\n",query(0,1,n,a,b,k)); } } }