求调，主席树全WA能过样例

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
	int cnt;
	int ls,rs;
}t[N*50];
int a[N];
int n,m,cnt;
int root[N],tot;

int clone(int x){
	t[++cnt]=t[x];
	return cnt;
}
void pushup(int x){
	t[x].cnt=t[t[x].ls].cnt+t[t[x].rs].cnt;
}

int build(int x,int l,int r,int k){
	x=clone(x);
	if(l==r){
		t[x].cnt++;
		return x;
	}
	int mid=l+r>>1;
	if(k<=mid) t[x].ls=build(t[x].ls,l,mid,k);
	else t[x].rs=build(t[x].rs,mid+1,r,k);
	pushup(x);
	return x;
}

int getans(int r1,int r2,int l,int r,int ql){
	if(l==r){
		return l;
	}
	int mid=l+r>>1,ls1=t[r1].ls,ls2=t[r2].ls,rs1=t[r1].rs,rs2=t[r2].rs;
	if(t[ls2].cnt-t[ls1].cnt>=ql) return getans(ls1,ls2,l,mid,ql);
	else return getans(rs1,rs2,mid+1,r,ql-t[ls2].cnt+t[ls1].cnt);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
    	scanf("%d", &a[i]);
    	root[++tot]=build(root[tot-1],0,1e9,a[i]);
	}
	while(m--){
		int y,x,k;
		scanf("%d%d%d", &x, &y, &k);
		printf("%d\n",getans(root[x-1],root[y],0,1e9,k));
	}
    return 0;
}