主席树板子

int n,q;
int tot;
#define ls ch[rt][0]
#define rs ch[rt][1]
#define vl ch[vs][0]
#define vr ch[vs][1]
int rt[M];
int ch[M<<5][2];
int val[M<<5];
int a[M],b[M];
int m;
int qr(int x){return (lower_bound(b,b+m,x) - b) +1 ;
}
int qr(int rt,int vs,int l,int r,int k){if(l==r)return l;int mid = l+r>>1;int v= val[ls] - val[vl];if(k<=v)return qr(ls,vl,l,mid,k);else return qr(rs,vr,mid+1,r,k-v);
}
void upd(int &rt,int vs,int l,int r,int k){rt=++tot;ls=vl;rs=vr;val[rt]=val[vs]+1;if(l==r)return;int mid=l+r>>1;if(k<=mid)upd(ls,vl,l,mid,k);else upd(rs,vr,mid+1,r,k);
}void solve(){cin>>n>>q;rep(i,1,n){cin>>a[i];b[i-1]=a[i];}sort(b,b+n);m =unique(b,b+n) - b;rep(i,1,n){upd(rt[i],rt[i-1],1,n,qr(a[i]));}rep(i,1,q){int l,r,k;cin>>l>>r>>k;cout<<b[qr(rt[r],rt[l-1],1,n,k)-1]<<endl;}
}