主席树板子题

#include <bits/stdc++.h>
#define N 200001
using namespace std;
int n,m,l,r,k,Ed[N],tot;
int a[N],X[N],cnt,A[N];
struct Tree{int ls,rs,sum;}T[N*25];
inline void build(int &now,int l,int r)
{
    now=++tot;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(T[now].ls,l,mid);
    build(T[now].rs,mid+1,r);
}
inline void update(int &now,int last,int l,int r,int val)
{
    now=++tot;
    T[now].ls=T[last].ls;
    T[now].rs=T[last].rs;
    T[now].sum=T[last].sum+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(val<=mid) update(T[now].ls,T[last].ls,l,mid,val);
    else update(T[now].rs,T[last].rs,mid+1,r,val);
}
inline int find_pos(int x)
{
    int l=1,r=cnt;
    while (l<r)
    {
        int mid=(l+r+1)>>1;
        if (X[mid]<=x) l=mid;
        else r=mid-1;
    }
    return l;
}
inline int ask(int to,int from,int l,int r,int k)
{
    if(l==r) return l;
    int num=T[T[to].ls].sum-T[T[from].ls].sum;
    int mid=l+r>>1;
    if(k<=num) return ask(T[to].ls,T[from].ls,l,mid,k);
    else return ask(T[to].rs,T[from].rs,mid+1,r,k-num);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     scanf("%d",&a[i]),A[i]=a[i];
    sort(A+1,A+1+n);
    for(int i=1;i<=n;i++)
     if(i==1||A[i]!=A[i-1])
      X[++cnt]=A[i];
    build(Ed[0],1,cnt); //建立一棵空树
    for(int i=1;i<=n;i++)
    {
        a[i]=find_pos(a[i]);
        update(Ed[i],Ed[i-1],1,cnt,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",X[ask(Ed[r],Ed[l-1],1,cnt,k)]);
    }
    return 0;
}