可持久化线段树求条QWQ (=´ω｀=)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=6e6+10;
int tot,n,m,l,r,k;
int sum[N],rt[N],ls[N],rs[N];
int a[N],ind[N],len;
int getid(const int &val){//lisanhua??? 
  return lower_bound(ind+1,ind+len+1,val)-ind;
}
int build(int l,int r){
    int root=tot++;
    if(l==r) return root;
    int mid=l+r>>1;
    ls[root]=build(l,mid);
    rs[root]=build(mid+1,r);
    return root;
}
int update(int k,int l,int r,int root){
    int dir=tot++;
    ls[dir]=ls[root];
	rs[dir]=rs[root];
	sum[dir]=sum[root]+1;
    if(l==r) return dir;
    int mid=l+r>>1;
    if(k<=mid)
        ls[dir]=update(k,l,mid,ls[dir]);
    else
        rs[dir]=update(k,mid+1,r,rs[dir]);
    return dir;
}
int query(int u,int v,int l,int r,int k){
    int mid=l+r>>1,
    x=sum[ls[v]]-sum[ls[u]];
    if(l==r) return l;
    if(k<=x)
        return query(ls[u],ls[v],l,mid,k);
    else 
        return query(rs[u],rs[v],mid+1,r,k-x);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	} 
    memcpy(ind,a,sizeof ind);//memcpy:复制 ？ 
    sort(ind+1,ind+n+1);
    len=unique(ind+1,ind+n+1)-ind-1;//unique:去重 
    rt[0]=build(1,len);
	for(int i=1;i<=n;i++){
		rt[i]=update(getid(a[i]),1,len,rt[i-1]);
	}
    while(m--){
        cin>>l>>r>>k;
        int s=query(rt[l-1],rt[r],1,len,k);
        printf("%lld\n",ind[s]);
    }
}