【模板】可持久化线段树 2(Persistent Segment Tree 2)

题目描述

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

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

输入格式

第一行包含两个整数，分别表示序列的长度 $n$ 和查询的个数 $m$。
第二行包含 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个元素 $a_i$。
接下来 $m$ 行每行包含三个整数 $l, r, k$ , 表示查询区间 $[l, r]$ 内的第 $k$ 小值。

输出格式

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

样例输入 #1

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

样例输出 #1

6405
15770
26287
25957
26287

数据范围

样例 1 解释

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

• 第一次查询为 $[2, 2]$ 区间内的第一小值，即为 $6405$。
• 第二次查询为 $[3, 4]$ 区间内的第一小值，即为 $15770$。
• 第三次查询为 $[4, 5]$ 区间内的第一小值，即为 $26287$。
• 第四次查询为 $[1, 2]$ 区间内的第二小值，即为 $25957$。
• 第五次查询为 $[4, 4]$ 区间内的第一小值，即为 $26287$。

数据规模与约定

• 对于 $10\%$ 的数据，满足 $1 \leq n,m \leq 10$。
• 对于 $25\%$ 的数据，满足 $1 \leq n,m \leq 10^3$。
• 对于 $40\%$ 的数据，满足 $1 \leq n,m \leq 10^5$。
• 对于 $50\%$ 的数据，满足 $1 \leq n,m \leq 2\times 10^5$，$0\le a_i \leq 2\times 10^5$。
• 对于所有数据，满足 $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$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接