#O1049. 区间第 k 小

区间第 k 小

题目描述

给定长度为 nn 的序列 aa,回答 qq 次询问:每次给出 l,r,kl, r, k,求 al∼ara_l \sim a_r 中第 kk 小的数。

题目类型

主席树、可持久化线段树

输入格式

第一行两个整数 n,qn, q。

第二行 nn 个整数。

接下来 qq 行,每行三个整数 l,r,kl, r, k。

输出格式

共 qq 行,每行一个整数表示答案。

样例 #1

样例输入 #1

5 2
5 3 1 4 2
1 5 3
2 4 2

样例输出 #1

3
3

数据规模与约定

数据范围 说明
1≤n,q≤2×1051 \le n, q \le 2 \times 10^5 长度与询问数
1≤ai≤1091 \le a_i \le 10^9 数值范围
1≤k≤r−l+11 \le k \le r-l+1 询问合法
  • 对值域建主席树,第 rr 版与第 l−1l-1 版做差后在线段树上找第 kk 小。