P3834 【模板】可持久化线段树 2

这是个非常经典的可持久化权值线段树入门题——静态区间第 $k$ 小。 **数据已经过加强，请使用可持久化权值线段树。同时请注意常数优化**。

如题，给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $[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$。 ### 数据规模与约定 - 对于 $20\%$ 的数据，满足 $1 \leq n,m \leq 10$。 - 对于 $50\%$ 的数据，满足 $1 \leq n,m \leq 10^3$。 - 对于 $80\%$ 的数据，满足 $1 \leq n,m \leq 10^5$。 - 对于 $100\%$ 的数据，满足 $1 \leq n,m \leq 2\times 10^5$，$0\le a_i \leq 10^9$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r - l + 1$。