#MYD8. 区间第 k 小
区间第 k 小
题目描述
给定一个长度为 n 的整数序列 a_1, …, a_n。有 q 次询问,每次给定 l, r, k,请你输出 a_l, a_{l+1}, …, a_r 中第 k 小的值(按数值升序排列后的第 k 个,重复值分别计数)。
输入格式
第一行两个整数 n 和 q。第二行 n 个整数 a_i。接下来 q 行,每行三个整数 l, r, k。
输出格式
共 q 行,每行一个整数,表示对应询问的答案。
数据范围
1 ≤ n, q ≤ 100000,0 ≤ a_i ≤ 10^9,1 ≤ l ≤ r ≤ n,1 ≤ k ≤ r − l + 1。
样例
5 3
4 1 5 2 3
1 5 2
2 4 1
3 5 3
2
1
5
说明/提示
主席树、归并树或整体二分均可。
解析
思路(主席树):按位置建立可持久化线段树(值域线段树),第 r 版减第 l−1 版后第 k 小即区间第 k 小。
复杂度:O((n+q) log V),V 为值域规模(离散化后 n)。
来源
人工命题 · 三方对比实验