区间第 k 小

【题目描述】

给定一个长度为 $N$ 的整数序列 $a_0, a_1, ..., a_{N-1}$。

请按顺序处理以下 $Q$ 个查询：

• $l_i$ $r_i$ $k_i$：输出 $(a_{l_i}, a_{l_i + 1}, ..., a_{r_i - 1})$ 中第 $k_i+1$ 小的值。

【输入】

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$l_0$ $r_0$ $k_0$
$l_1$ $r_1$ $k_1$
:
$l_{Q-1}$ $r_{Q-1}$ $k_{Q-1}$

【输出】

对于每个查询，输出一行一个整数，表示对应区间中第 $k_i+1$ 小的值。

【输入样例】

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

【输出样例】

1
4
1

【数据范围】

• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $0 \leq a_i \leq 1000000000$
• $0 \leq l_i < r_i \leq N$
• $0 \leq k_i < r_i - l_i$

【来源】

Library Checker（yosupo06） range_kth_smallest