njupt（1406-第K小的数）

第K小的数

时间限制(普通/Java) : 1000 MS/ 3000 MS          运行内存限制 : 65536 KByte
总提交 : 101            测试通过 : 30 

比赛描述

你为SKZ公司的数据结构部门工作，你的工作是重新写一个程序，这个程序能快速地找到一段数列中第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个数，代表数列的元素，所有数都不相同，而且不会超过109 。

接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j−i+1。

输出

输出每个查询的答案，用换行符隔开。

样例输入

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

样例输出

5
6
3

代码超时（参考网上的伴随矩阵的用法）

http://blog.csdn.net/v_JULY_v/article/details/6452100

#include<iostream>  
#include<algorithm>  
using namespace std;  
  
struct node{  
    int num,data;  
    bool operator < (const node &p) const   
    {  
        return data < p.data;  
    }  
};  
node p[100001];  
  
int main()  
{  
    int n,m,i,j,a,b,c;
    while(scanf("%d %d",&n,&m)!=EOF)   
    {  
        for(i=1;i<=n;i++)   
        {  
            scanf("%d",&p[i].data);  
            p[i].num = i;  
        }  
        sort(p+1,p+1+n);  
          
        for(j=1;j<=m;j++)   
        {  
            scanf("%d %d %d",&a,&b,&c);  
            for(i=1;i<=n;i++)   
            {  
                if(p[i].num>=a && p[i].num<=b)   
                    c--;   
                if(c == 0)   
                    break;  
            }  
            printf("%d
",p[i].data);  
        }  
    }  
    return 0;  
}