区间第K小

题目描述:

 

给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

 

输入格式:

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数l, r, k , 表示查询区间[l, r]内的第k小值。

输出格式:

输出包含k行，每行1个正整数，依次表示每一次查询的结果

样例输入:

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

样例输出:

6405
15770
26287
25957
26287

提示:

这是个非常经典的主席树入门题——静态区间第K小

请使用主席树。

数据范围：

对于100%的数据满足：1<=N,M<=2*10⁵

对于数列中的所有数ai​，均满足−10⁹≤ai​≤10⁹

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为[25957, 6405, 15770, 26287, 26465 ][25957,6405,15770,26287,26465]

第一次查询为[2, 2][2,2]区间内的第一小值，即为6405

第二次查询为[3, 4][3,4]区间内的第一小值，即为15770

第三次查询为[4, 5][4,5]区间内的第一小值，即为26287

第四次查询为[1, 2][1,2]区间内的第二小值，即为25957

第五次查询为[4, 4][4,4]区间内的第一小值，即为26287

时间限制: 1500ms
空间限制: 256MB

---