给定静态序列 $\{a_n\}$，若干次询问求区间 $[l_i,r_i]$ 中第 $k_i$ 大的数。

一个最为简单的方法是，对 $\forall i\in[1,n],a_{1\cdots i}$ 开 $n$ 棵权值线段树进行统计。

对 $\{a_n\}$ 进行离散化后，每次询问只需要从第 $l_{i-1}$ 棵线段树和第 $r_i$ 棵线段树的根节点开始遍历，每次求出当前第 $l_{i-1}$ 及第 $r_i$ 棵线段树的左儿子代表的权值区间中的数字个数，并进行相减，即可求出左儿子所代表的权值区间包含了多少个 $a_{l_i\cdots r_i}$，即可判断第 $k_i$ 大的数会落在左儿子还是右儿子代表的区间内。

其实我们可以发现，这 $n$ 棵线段树有许多重复的部分。

对于第 $i$ 棵和第 $i+1$ 棵线段树，实际上我们可以看做是将 $a_{i+1}$ 插入第 $i$ 棵中，而由于这个操作只会对 $O(\log n)$ 个区间造成变化，我们即可通过动态开点线段树来存储这 $n$ 个线段树。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m,a[N+5],b[N+5],root[N+5],ls[(N<<5)+5],rs[(N<<5)+5],sum[(N<<5)+5],tot;
int build(int l,int r){
    int p=++tot;
    if (l==r) return p;
    int Mid=(l+r)>>1;
    ls[p]=build(l,Mid);
    rs[p]=build(Mid+1,r);
    return p;
}
int insert(int p0,int l,int r,int k){ // 从节点p0复制到一个新节点并修改
    int p=++tot;
    ls[p]=ls[p0],rs[p]=rs[p0],sum[p]=sum[p0];
    if (l==r){
        sum[p]++;
        return p;
    }
    int Mid=(l+r)>>1;
    if (k<=Mid) ls[p]=insert(ls[p0],l,Mid,k);
    else rs[p]=insert(rs[p0],Mid+1,r,k);
    sum[p]=sum[ls[p]]+sum[rs[p]];
    return p;
}
int query(int p,int q,int l,int r,int k){
    if (l==r) return l;
    int t=sum[ls[q]]-sum[ls[p]],Mid=(l+r)>>1;
    if (k<=t) return query(ls[p],ls[q],l,Mid,k);
    return query(rs[p],rs[q],Mid+1,r,k-t);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int t=unique(b+1,b+n+1)-b-1;
    root[0]=build(1,t);
    for (int i=1;i<=n;i++){
        int x=lower_bound(b+1,b+t+1,a[i])-b;
        root[i]=insert(root[i-1],1,t,x);
    }
    for (int i=1,l,r,k;i<=m;i++){
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",b[query(root[l-1],root[r],1,t,k)]);
    }
    return 0;
}