#1064. 【模板】可持久化线段树 2(静态区间第 k 小)

【模板】可持久化线段树 2(静态区间第 k 小)

题目描述

如题,给定 nn 个整数构成的序列 aa,将对于指定的闭区间 [l,r][l, r] 查询其区间内的第 kk 小值。

输入格式

第一行包含两个整数,分别表示序列的长度 nn 和查询的个数 mm。
第二行包含 nn 个整数,第 ii 个整数表示序列的第 ii 个元素 aia_i。
接下来 mm 行每行包含三个整数 l,r,k l, r, k , 表示查询区间 [l,r][l, r] 内的第 kk 小值。

输出格式

对于每次询问,输出一行一个整数表示答案。

样例

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

题目来源:洛谷 P3834