关于在指定区间求第k小的数，求高效率算法
给定一个整数数列a[1..n]，其中每个元素都不相同，你的程序要能回答一组格式为Q (i , j , k)的查询，Q(i, j ,k)的意思是“在a[i..j]中第k小的数是多少？”
例如令 a = {1, 5, 2, 6, 3, 7, 4}，查询格式为Q (2 , 5 , 3)，数列段a[2..5] = {5, 2, 6, 3}，第3小的数是5，所以答案是5。
第一行包括一个正整数n，代表数列的总长度，还有一个数m，代表有m个查询。n、m满足：1≤n≤100 000，1≤m≤5 000。
第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过10^9
接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j?i+1。
关于这个问题可能已经讨论了很多次，但是我用快排的变形还是超时，希望能看更高效的算法
[解决办法]
lz搜索一下划分树的资料吧，以前看过，不过我现在也记不太清楚了。
[解决办法]
我是这么理解的，每一次查询就是一次新的，相对于m个查询一直做是比较笨的，但我想不到高级的怎么做，所以我现在只写了一下在n个数中找第k小的数。
//生成测试文件
#include <fstream>
#include <vector>
#include <Windows.h>
#include <algorithm>
#include <iterator>
using namespace std;
void main()
{
srand(GetTickCount());
vector<size_t> nums;
unsigned prenum=0;
ofstream of("testfile.txt", ios_base::out);
for (size_t i = 0 ; i < 10; ++i)
{
prenum += rand() % 3;
nums.push_back(prenum);
}
random_shuffle(nums.begin(), nums.end());
copy(nums.begin(), nums.end(), ostream_iterator<size_t>(of, " "));
}
//读入，查找
#include <vector>
#include <set>
#include <fstream>
#include <iostream>
using namespace std;
#define K 3
void main()
{
vector<size_t>Nums;
ifstream inf("testfile.txt", ifstream::in);
size_t tmp;
inf>>tmp;
while (inf)
{
Nums.push_back(tmp);//读入数字，这个的效率还可以改进，简单，现在不考虑
inf>>tmp;
}
set<size_t,greater<size_t> > last;//存储K个最小值，从大到小排序
for (size_t i = 0 ; i < K ; i++)
{
last.insert(Nums[i]);//先放入K个值
}
for (vector<size_t>::const_iterator p = Nums.begin() + K; p != Nums.end(); ++p)
{
if(*p < *last.begin())
{//当当前数小于树里的最大值时
last.erase(last.begin());
last.insert(*p);
}
}
cout<<*last.begin()<<endl;
}
