#21403. 可持久化线段树

这是个非常经典的可持久化权值线段树入门题——静态区间第 k 小。

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

第一行包含两个整数，分别表示序列的长度 n 和查询的个数 m。

第二行包含 n 个整数，第 i 个整数表示序列的第 i 个元素 a_i ​

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

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

样例 1 解释

n=5，数列长度为 5，数列从第一项开始依次为{25957,6405,15770,26287,26465}。

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

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

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

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

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

对于 的数据，满足 。

对于 的数据，满足

对于 的数据，满足

对于 的数据，满足 。