码风可能有点怪，因为不喜欢加空格（

#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

class PresistentSegmentTree {
    public:
        PresistentSegmentTree(int size,int *init) {
            size_=size;
            nodestop_=0;
            nodes=new node[size<<5]();
            roots=new int[size+1]();
            roots[0]=NewNode();
            InitBuild(1,size,roots[0]);
            for(int i=1;i<=size;i++) { //依次插入数值。
                roots[i]=NewNode();
                InsertChain(init[i],1,size,roots[i],roots[i-1]);
            }
        }

        //Note the it asks for the kth minimum number.
        //注意是找的第 k 小值。
        int RangeQuery_kth(int range_lower_bound,int range_upper_bound,int k) {
            //下界减一是因为前缀和应该是 sum[r]-sum[l-1]。
            return RangeQuery_kth_Base(k,1,size_,
                roots[range_lower_bound-1],roots[range_upper_bound]);
        }

        //Provided for debug.
        //Debug 用，输出 p 为根的子树。
        void PrintTree(int l,int r,int p) {
            cout<<p<<' '<<nodes[p].num_count_sum<<endl;
            if(l==r) return ;
            int mid=(l+r)>>1;
            PrintTree(l,mid,nodes[p].left_son);
            PrintTree(mid+1,r,nodes[p].right_son);
        }

        ~PresistentSegmentTree() {delete []nodes; delete []roots;}

    private:
        int size_;

        //A segment tree node.
        //线段树结点。
        struct node {
            int num_count_sum;
            int left_son,right_son;
            node():num_count_sum(0),left_son(0),right_son(0) {}
            node(int prefix_cnt_sum_,int left_son_,int right_son_) 
                :num_count_sum(prefix_cnt_sum_),
                left_son(left_son_),right_son(right_son_) {}
        };
        node *nodes;
        int nodestop_; //结点指针

        int *roots;

        int NewNode() {return ++nodestop_;}
        int NewNode(int num_count_sum,int left_son,int right_son) {
            nodes[++nodestop_]=node(num_count_sum,left_son,right_son);
            return nodestop_;
        } 

        void InitBuild(int l,int r,int p) {
            if(l==r) return ;
            int mid=(l+r)>>1;
            nodes[p].left_son=NewNode();
            nodes[p].right_son=NewNode();
            InitBuild(l,mid,nodes[p].left_son);
            InitBuild(mid+1,r,nodes[p].right_son);
        }

        void PushUp(int p) {
            nodes[p].num_count_sum=nodes[nodes[p].left_son].num_count_sum
                +nodes[nodes[p].right_son].num_count_sum;
        }

        //Insert a chain in the tree.
        //p is the node in the tree inserting now.
        //q is the node corresponding p in the original tree.
        //向可持久化线段树插入一条链。当前点为 p，原树对应节点为 q。
        void InsertChain(int insert_value,int l,int r,int p,int q) {
            if(l==r) {nodes[p].num_count_sum++; return ;}
            int mid=(l+r)>>1;
            if(insert_value<=mid) {
                nodes[p].right_son=nodes[q].right_son;
                nodes[p].left_son=NewNode();
                InsertChain(insert_value,l,mid,
                    nodes[p].left_son,nodes[q].left_son);
            }
            else {
                nodes[p].left_son=nodes[q].left_son;
                nodes[p].right_son=NewNode();
                InsertChain(insert_value,mid+1,r,
                    nodes[p].right_son,nodes[q].right_son);
            }
            PushUp(p);
        }

        //Using binary search on segment tree.
        //p represent the node of the tree of lower bound, which range's [l,r].
        //While q means the upper bound.
        //线段树上二分，p 是左闭区间对应的线段树的结点，q 则是右闭区间。
        int RangeQuery_kth_Base(int k,int l,int r,int p,int q) {
            if(l==r) return l;
            int mid=(l+r)>>1;
            int num_count_sum_now=nodes[nodes[q].left_son].num_count_sum
                -nodes[nodes[p].left_son].num_count_sum;
            if(k<=num_count_sum_now) return RangeQuery_kth_Base(k,l,mid,
                nodes[p].left_son,nodes[q].left_son);
            return RangeQuery_kth_Base(k-num_count_sum_now,mid+1,r,
                nodes[p].right_son,nodes[q].right_son);
        }
};

int n,m;
int a[200005];
int b[200005],a_rank[200005];

signed main() {
    // freopen("P3834_3.in","r",stdin);
    // freopen("P3834_3.ans","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];

    //离散化
    stable_sort(b+1,b+1+n);
    int *bnend=unique(b+1,b+1+n);
    for(int i=1;i<=n;i++) a_rank[i]=lower_bound(b+1,bnend,a[i])-b;

    // for(int i=1;i<=n;i++) printf("%d ",a_rank[i]);
    // puts("");

    PresistentSegmentTree *segtree=new PresistentSegmentTree(n,a_rank);
    int query_l,query_r,query_k;
    while(m--) {
        scanf("%d%d%d",&query_l,&query_r,&query_k);
        int rank_k=segtree->RangeQuery_kth(query_l,query_r,query_k);
        printf("%d\n",b[rank_k]);
    }
    delete segtree;
    
    return 0;
}

提交记录