6701: 学习系列——线段树 VX —— 第 k 小数据
[Creator : ]
Description
给一个长度为 $n$ 的数组 $A$。
你的任务是给你 $m$ 次查询，对于每次查询在区间 $[l,r]$ 中找到第 $k$ 小的数据。
你的任务是给你 $m$ 次查询，对于每次查询在区间 $[l,r]$ 中找到第 $k$ 小的数据。
Input
第一行包括一个整数 $n\ (1 \leq n \leq 10^6)$，表示数组 $a$ 的长度。
第二行包括 $n$ 个整数，第 $i$ 个数字为 $A_i\ (-10^9 \leq A_i \leq 10^9)$。
第一行包括一个整数 $m\ (1 \leq m \leq 10^6)$，表示有 $m$ 次查询。
第 $4 \sim m+4$ 行，每行包括三个整数 $l,r,k$，表示查询区间 $[l,r]$ 间的第 $k$ 小整数。
第二行包括 $n$ 个整数，第 $i$ 个数字为 $A_i\ (-10^9 \leq A_i \leq 10^9)$。
第一行包括一个整数 $m\ (1 \leq m \leq 10^6)$，表示有 $m$ 次查询。
第 $4 \sim m+4$ 行，每行包括三个整数 $l,r,k$，表示查询区间 $[l,r]$ 间的第 $k$ 小整数。
Output
一共包括 $m$ 行，对于每次查询，输出区间 $[l,r]$ 间的第 $k$ 小整数。
Sample 1 Input
7
3 2 5 4 7 1 9
28
1 7 1
1 7 2
1 7 3
1 7 4
1 7 5
1 7 6
1 7 7
2 7 1
2 7 2
2 7 3
2 7 4
2 7 5
2 7 6
3 7 1
3 7 2
3 7 3
3 7 4
3 7 5
4 7 1
4 7 2
4 7 3
4 7 4
5 7 1
5 7 2
5 7 3
6 7 1
6 7 2
7 7 1
Sample 1 Output
1
2
3
4
5
7
9
1
2
4
5
7
9
1
4
5
7
9
1
4
7
9
1
7
9
1
9
9
对于区间 $[1,7]$ 而言，数据为 $[3,2,5,4,7,1,9]$，因此第 $1$ 小的数字为 $1$，第 $2$ 小的数字为 $2$，第 $3$ 小的数字为 $3$，第 $4$ 小的数字为 $4$，第 $5$ 小的数字为 $5$，第 $6$ 小的数字为 $7$，第 $7$ 小的数字为 $9$。