#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)。

来源

人工命题 · 三方对比实验