3537. [POJ 2104]K-th Number

【题目描述】

给定一个长度为 $N$ 的整数序列 A，执行 $M$ 次操作，其中第 $i$ 次操作给出三个整数 $l_i,r_i.k_i$。求 $A[l_i],A[l_i+1],...A[r_i]$ (即 A 的下标区间 $[l_i,r_i]$)中第 $k_i$ 小的数是多少。

【输入格式】

第一行一个正整数 $N$，表示序列 A 的大小，一个正整数 $M$，表示 $M$ 次询问。

第二行包含 $N$个不同的整数，其绝对值不超过 $10^9$.

接下来 $M$ 行，每行包含三个整数 $l_i,r_i,k_i$，用以描述第 $i$ 次操作。

【输出格式】

共有 $M$ 行，每行一个整数，表示查询的第 $k$ 小的数。

【样例输入】

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

【样例输出】

5
6
3

【数据规模与约定】

$1 \leq N \leq 10^5$

$1 \leq M \leq 5000$

$1 \leq l_i \leq r_i \leq n, l_i \leq k \leq r_i$

$|A[i]|\leq 10^9$

【来源】

《算法竞赛进阶指南》POJ2104