【模板】可持久化线段树 1(主席树)

题目背景

这是个非常经典的主席树入门题——静态区间第K小 **数据已经过加强,请使用主席树。同时请注意常数优化**

题目描述

如题,给定N个整数构成的序列,将对于指定的闭区间查询其区间内的第K小值。

输入输出格式

输入格式


第一行包含两个正整数N、M,分别表示序列的长度和查询的个数。 第二行包含N个整数,表示这个序列各项的数字。 接下来M行每行包含三个整数$ l, r, k$ , 表示查询区间$[l, r]$内的第k小值。

输出格式


输出包含k行,每行1个整数,依次表示每一次查询的结果

输入输出样例

输入样例 #1

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出样例 #1

6405
15770
26287
25957
26287

说明

**数据范围**: 对于20%的数据满足:$1 \leq N, M \leq 10$ 对于50%的数据满足:$1 \leq N, M \leq 10^3$ 对于80%的数据满足:$1 \leq N, M \leq 10^5$ 对于100%的数据满足:$1 \leq N, M \leq 2\cdot 10^5$ 对于数列中的所有数$a_i$,均满足$-{10}^9 \leq a_i \leq {10}^9$ **样例数据说明**: N=5,数列长度为5,数列从第一项开始依次为$[25957, 6405, 15770, 26287, 26465 ]$ 第一次查询为$[2, 2]$区间内的第一小值,即为6405 第二次查询为$[3, 4]$区间内的第一小值,即为15770 第三次查询为$[4, 5]$区间内的第一小值,即为26287 第四次查询为$[1, 2]$区间内的第二小值,即为25957 第五次查询为$[4, 4]$区间内的第一小值,即为26287