#O1049. 区间第 k 小
区间第 k 小
题目描述
给定长度为 的序列 ,回答 次询问:每次给出 ,求 中第 小的数。
题目类型
主席树、可持久化线段树
输入格式
第一行两个整数 。
第二行 个整数。
接下来 行,每行三个整数 。
输出格式
共 行,每行一个整数表示答案。
样例 #1
样例输入 #1
5 2
5 3 1 4 2
1 5 3
2 4 2
样例输出 #1
3
3
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 长度与询问数 | |
| 数值范围 | |
| 询问合法 |
- 对值域建主席树,第 版与第 版做差后在线段树上找第 小。