题面说$|a_i|<1e9$，我开的1e6,没离散化，过了？

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int tr[N<<5],ls[N<<5],rs[N<<5],root[N],tot=0;
inline void pushup(int x){
	tr[x]=tr[ls[x]]+tr[rs[x]];
}
void build(int &x,int l,int r){
	x=++tot;
	if(l==r) return;
	int mid=(l+r)/2;
	build(ls[x],l,mid),build(rs[x],mid+1,r);
	pushup(x);
}
void insert(int u,int &x,int l,int r,int k){
	x=++tot;
	tr[x]=tr[u]+1,ls[x]=ls[u],rs[x]=rs[u];
	if(l==r)  return; 
	int mid=(l+r)/2;
	if(k<=mid) insert(ls[u],ls[x],l,mid,k);
	else insert(rs[u],rs[x],mid+1,r,k);
}
int query(int u,int v,int l,int r,int k){
	int mid=(l+r)/2,lx=tr[ls[v]]-tr[ls[u]];
	if(l==r) return l;
	if(k<=lx) return query(ls[u],ls[v],l,mid,k);
	return query(rs[u],rs[v],mid+1,r,k-lx);
}
int n,m;
int main(){
	cin>>n>>m;
	build(root[0],0,1e6);
	for(int i=1;i<=n;i++){
		int t;
		cin>>t;
		insert(root[i-1],root[i],0,1e6,t);
	}
	while(m--){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<query(root[l-1],root[r],0,1e6,k)<<endl;
	}
}