【模板】可持久化线段树 2
作业已超过截止时间,您无法递交本题目。
题目背景
这是个非常经典的可持久化权值线段树入门题——静态区间第 \(k\) 小。
题目描述
给定 \(n\) 个整数构成的序列 \(a\),将对于指定的闭区间 \([l, r]\) 查询其区间内的第 \(k\) 小值。
格式
输入格式
第一行包含两个整数,分别表示序列的长度 \(n\) 和查询的个数 \(m\)。
第二行包含 \(n\) 个整数,第 \(i\) 个整数表示序列的第 \(i\) 个元素 \(a_i\)。
接下来 \(m\) 行每行包含三个整数 \( l, r, k\) , 表示查询区间 \([l, r]\) 内的第 \(k\) 小值。
输出格式
对于每次询问,输出一行一个整数表示答案。
样例1
样例输入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
样例解释
\(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\),\(|a_i| \leq 10^9\),\(1 \leq l \leq r \leq n\),\(1 \leq k \leq r - l + 1\)。