区间第 k 小（Range Kth Smallest）

问题描述

给你一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$。请按顺序处理以下 $Q$ 个查询：

• l r k：输出区间 $(a_l, a_{l+1}, \dots, a_{r-1})$ 中第 $k+1$ 小的值（即下标从 0 开始的第 $k$ 小对应“$k+1$ 小”）。

约束条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$
• $0 \leq l < r \leq N$
• $0 \leq k < r - l$

输入格式

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

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

1
4
1