主席树晕氧RE求调

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;

#define int long long

int a[maxn];
int root[maxn],lv,h[maxn],raw[maxn],rh[maxn];

struct PersisitentArray {
	struct Node {
		int l,r,val,sum;
		Node operator=(const Node b) {
			l=b.l,r=b.r,val=b.val;
			return *this;
		}
	} v[maxn<<5];
	int psz=1;
	int clone(int r) {
		v[++psz]=v[r];
		return psz;
	}
	int pushup(int u) {
		v[u].sum=v[v[u].l].sum+v[v[u].r].sum;
	}
	void build(int u,int l,int r) {
		if(l==r) {
			return;
		}
		int mid=l+r>>1;
		v[u].l=clone(0),v[u].r=clone(0);
		build(v[u].l,l,mid),build(v[u].r,mid+1,r);
		pushup(u);
	}
	int add(int u,int l,int r,int x) {
		u=clone(u);
		if(l==r) {
			v[u].val+=1;
			v[u].sum+=1;
			return u;
		}
		int mid=l+r>>1;
		if(x<=mid) v[u].l=add(v[u].l,l,mid,x);
		else v[u].r=add(v[u].r,mid+1,r,x);
		pushup(u);
		return u;
	}
	
	int query(int u,int l,int r,int x) {
		if(l==r) return v[u].val;
		int mid=l+r>>1;
		if(x<=mid) return query(v[u].l,l,mid,x);
		else return query(v[u].r,mid+1,r,x);
	}
	
	int Mquery(int ul,int ur,int l,int r,int k) {
		if(l==r) return raw[l];
		int mid=l+r>>1;
		int sl=v[v[ur].l].sum-v[v[ul].l].sum;
		if (sl<=k)
			return Mquery(v[ul].r,v[ur].r,mid+1,r,k-sl);
		else
			return Mquery(v[ul].l,v[ur].l,l,mid,k);
	}
		
}pst;
int debug_v;
signed main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],raw[i]=a[i];
	sort(raw+1,raw+1+n);
	int tn=unique(raw+1,raw+1+n)-raw-1;
	for(int i=1;i<=n;i++) h[i]=upper_bound(raw+1,raw+1+tn,a[i]-1)-raw;
	for(int i=1;i<=n;i++) rh[h[i]]=a[i];

	pst.build(root[0]=1,1,tn);
	
	for(int i=1;i<=n;i++) root[i]=pst.add(root[i-1],1,tn,h[i]);
	while(m--) {
		int l,r,k;
		cin>>l>>r>>k;
		cout<<pst.Mquery(root[l-1],root[r],1,tn,k-1)<<'\n';
	}
}