莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 离散化数值
2. 构造 n 个版本的线段树
3. 二分区间答案

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n,m;
int a[N];
int root[N],idx;
vector<int> nums;
struct Node
{
    int l,r;
    int cnt;
}tr[N*21];

int find(int x)
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

int build(int l,int r)
{
    int p=++idx;
    if(l==r) return p;
    int mid=l+r>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}

int insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];

    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }

    int mid=l+r>>1;
    if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);
    else tr[q].r=insert(tr[p].r,mid+1,r,x);

    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;

    return q;
}

int query(int q,int p,int l,int r,int k)
{
    if(l==r) return l;

    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;

    int mid=l+r>>1;
    if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        nums.push_back(a[i]);
    }

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    root[0]=build(0,nums.size()-1);

    for(int i=1;i<=n;i++) root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));

    int l,r,k;
    while(m--)
    {
        cin>>l>>r>>k;
        cout<<nums[query(root[r],root[l-1],0,nums.size()-1,k)]<<endl;
    }

    return 0;
}