Preparing NOJ

第K小的数

1000ms 65536K

Description:

你为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。

Input:

第一行包括一个正整数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。

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

Note:

 

本题由旧版NOJ导入,来源:JSOI2010

Info

NOJ

Provider NOJ

Code NOJ1406

Tags

Submitted 5

Passed 1

AC Rate 20%

Date 04/20/2019 10:03:10

Related

Nothing Yet