HDU 2665 chairman tree (static) asks interval K small template problem.

#include <bits/stdc++.h>
using namespace std;
const int M = 1e5+7;
int _,n,q,a[M],ls[M];
int L[M*20],R[M*20],num[M*20],T[M],tot,pos;//LThe left sub tree of each node, R, the right subtree of each node, and T store all the nodes.
void build(int l,int r,int &rt){
    rt=++tot;
    num[rt]=0;//Empty trees do not have numbers.
    if(l==r){
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,L[rt]);
    build(mid+1,r,R[rt]);
}
void update(int l,int r,int &rt,int prert){
    rt=++tot;
    num[rt]=(num[prert]+1);//The number is 1 more than the previous tree.
    if(l==r){
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid){
        R[rt]=R[prert];//Only the left child tree is updated, and the right subtree state is the same as the previous tree.
        update(l,mid,L[rt],L[prert]);
    }
    else{
        L[rt]=L[prert];//Update the right subtree only, and the left sub tree state is the same as the previous tree.
        update(mid+1,r,R[rt],R[prert]);
    }
}
int query(int l,int r,int lrt,int rrt,int k){
    if(l==r){
        return l;
    }
    int mid=(l+r)>>1;
    int sum=num[L[rrt]]-num[L[lrt]];//The R tree minus the L-1 tree is the number of queries in the current interval.
    if(sum>=k) return query(l,mid,L[lrt],L[rrt],k);
    else return query(mid+1,r,R[lrt],R[rrt],k-sum);
}
void solve(){
    sort(ls+1,ls+n+1);
    int sz=unique(ls+1,ls+n+1)-ls-1;//De discrete
    build(1,sz,T[0]);//Hollow tree
    for(int i=1;i<=n;i++){
        pos=lower_bound(ls+1,ls+sz+1,a[i])-ls;
        update(1,sz,T[i],T[i-1]);
    }
    while(q--){
        int l,r,k,ans;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",ls[query(1,sz,T[l-1],T[r],k)]);//The state of the query interval is reduced from the first R tree to the L-1 tree.
    }
}
int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&q);tot=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),ls[i]=a[i];
        solve();
    }
    return 0;
}