区间第k大（静态）——主席树

区间第k大（静态）——主席树

Description

给定一个长度为n的序列，m个询问，每个询问的形式为：L，r，k表示在[L,r]间中的第k大元素。

Input

第1行：2个数，n,m表示序列的长度和询问的个数
第2行：n个数，表示n个数的大小
第3-m+2行：每行3个数，L，r，k表示询问在[L,r]区间内第k小的元素

Output

对于每个询问，输出答案。

Sample Input

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

Sample Output

3 2

Hint

对于100%的数据，n<=100000, m<=100000,1<=L<=r<=n, 1<=k<=r-L+1

主席树入门级题目，我们维护的是权值线段树。

rt[x]表示第x个数当根的前x个线段树的根，于是就有了前缀和的性质，那么我们查询[l,r]的时候将rt[r]-rt[l-1]即可计算出来。

发现修改操作（单点修改）最多logn个点受影响，于是我们可以共用很多信息，动态开点修改链上的。（这道题太水。。。感觉没有突出主席树的强大功能（虽然难了我也不会））。

值得注意的是主席树的空间复杂度略高（貌似和树套树差不多啊。。。），开线段树的时候内存记得开大一点，经过刚才的理性分析，似乎也是nlogn级别的空间复杂度？