10pts,求条，必关

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Tree{
    struct str{
        int l,r,sum;
    };
    vector<str> tree;
    vector<int> root;
    void init(int x){root.push_back(build(1,x));}
    int build(int l,int r)
    {
        tree.push_back({-1,-1,0});
        int id=tree.size()-1;
        if(l==r) return id;
        int mid=(l+r)>>1;
        tree[id].l=build(l,mid);
        tree[id].r=build(mid+1,r);
        return id;
    }
    int update(int pre,int l,int r,int pos)
    {
        tree.push_back(tree[pre]);
        int id=tree.size()-1;
        tree[id].sum++;
        if(l==r) return id;
        int mid=(l+r)>>1;
        if(pos<=mid) tree[id].l=update(tree[pre].l,l,mid,pos);
        else tree[id].r=update(tree[pre].r,mid+1,r,pos);
        return id;
    }
    int ask(int y,int x,int l,int r,int k)
    {
        if(l==r) return l;
        int mid=(l+r)>>1;
        int lcnt=tree[tree[x].l].sum-tree[tree[y].l].sum;
        if(lcnt>=k) return ask(tree[y].l,tree[x].l,l,mid,k);
        else return ask(tree[y].r,tree[x].r,mid+1,r,k-lcnt);
    }
};
int main()
{
    scanf("%d%d",&n,&m);
    vector<int> a(4*n),sa(4*n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        sa[i]=a[i];
    }
    sort(sa.begin(),sa.end());  
    sa.erase(unique(sa.begin(),sa.end()),sa.end());
    int len=sa.size();
    auto rank=[&](int x)
    {
        return lower_bound(sa.begin(),sa.end(),x)-sa.begin()+1;
    };
    Tree pt;
    pt.init(len);
    for(int j=0;j<n;j++)
    {
        int rk=rank(a[j]);
        int nrt=pt.update(pt.root[j],1,len,rk);
        pt.root.push_back(nrt);
    }
    while(m--)
    {
        int l,r,s;
        scanf("%d%d%d",&l,&r,&s);
        int rak=pt.ask(pt.root[l-1],pt.root[r],1,len,s);
        printf("%d\n",sa[rak-1]); 
    }
    return 0;
}