Description
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.
Input
The second line contains n different integer numbers not exceeding 10 9 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 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
Output
Sample Input
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
Sample Output
5 6 3
Hint
This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.
题目意思：给一个数组。问一个区间内第K大的数。
解题思路：划分树。
划分树是基于高速排序的，首先将原始数组a[]进行排序sorted[]，然后取中位数m，将未排序数组中小于m放在m左边，大于m的放在m右边，并记下原始数列中每一个数左边有多少数小于m，用数组to_left[depth][]表示，这就是建树过程。
重点在于查询过程。设[L,R]为要查询的区间，[l,r]为当前区间，s 表示[L,R]有多少数放到左子树，ss表示[l,L-1]有多少数被放倒左子树。假设s大于等于K，也就是说第K大的数肯定在左子树里。下一步就查询左子树，但这之前先要更新L,R，新的newl=l+ss, newr=newl+s-1。假设s小于k，也就是说第k大的数在右子树里，下一步查询右子树，也要先更新L,R，dd表示[l,L-1]中有多少数被放到右子树，d表示[L,R]有多少数被放到右子树，那么newl = m+1+dd，newr=m+d+dd, 这样查询逐渐缩小查询区间，直到最后L==R 返回最后结果即可。
给出一个大牛的图片样例。
代码：
}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5265373.html 如需转载请自行联系原作者
