题目名称	930. [河南省队2012] 找第k小的数
输入输出	`kth.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	wo shi 刘畅于2012-07-17加入
开放分组	全部用户
提交状态
分类标签	可持久化线段树可持久化 CDQ分治划分树树套树离散化
	分享题解

本题关联比赛
20120718

930. [河南省队2012] 找第k小的数

★★★ 输入文件：kth.in 输出文件：kth.out 简单对比
时间限制：1 s 内存限制：256 MiB

看到很短的题目会让人心情愉悦，所以给出一个长度为N的序列A1,A2,A3,...,AN，

现在有M个询问，每个询问都是Ai...Aj中第k小的数等于多少。

第一行两个正整数N，M。

第二行N个数，表示序列A1,A2,...,AN。

紧着的M行，每行三个正整数i,j,k(k≤j-i+1)，表示

询问Ai...Aj中第k小的数等于多少。

共输出M行，第i行输出第i个询问的答案。

1
3
4

询问区间的第k小值并非严格第k小，例如样例2中第4个询问，询问3到5中第2小的数，

答案输出9，并不是严格第2小的10。

在50%的数据中，1<=N<=10,000，1<=M<=10,000，A[i]<=100,000;

在100%的数据中，1<=N<=100,000,1<=M<=100,000,A[i]<=1,000,000;