所谓树套树，其本质是通过用树维护一组树的根，从而维护强悍的数据

1 线段树套平衡树

线段树套

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

#define MAXN 50005

int seg[MAXN<<2];
int amin=1000000,amax=0;

struct Node{
	int val,rnd,siz;
	int ch[2];	
}t[MAXN*80];
int tcnt=0;

int n,m;
int a[MAXN];
int rop,rl,rr,rk,rpos;
	
int nnode(int val){
	tcnt++;
	t[tcnt].ch[0]=0;
	t[tcnt].ch[1]=0;
	t[tcnt].val=val;
	t[tcnt].siz=1;
	t[tcnt].rnd=rand();

	return tcnt;
}
inline void upd(int id){
	t[id].siz=t[t[id].ch[0]].siz+t[t[id].ch[1]].siz+1;
} 
inline void split(int id,int val,int &x,int &y){
	if(!id){
		x=0;
		y=0;
		return;
	}
	if(t[id].val<=val){
		x=id;
		split(t[id].ch[1],val,t[id].ch[1],y);
		upd(id);
		return;
	}else{
		y=id;
		split(t[id].ch[0],val,x,t[id].ch[0]);
		upd(id);
		return;
	}
	return;
}
inline int merge(int x,int y){
	if((!x)||(!y)){
		return (x+y);
	}
	if(t[x].rnd<=t[y].rnd){
		t[x].ch[1]=merge(t[x].ch[1],y);
		upd(x);
		return x;
	}else{
		t[y].ch[0]=merge(x,t[y].ch[0]);
		upd(y);
		return y;
	}
}

inline int rnk(int& id,int val){
    int x,y;
    split(id, val-1, x, y);
    int k = t[x].siz+1;
    id = merge(x,y);
    return k;
}

inline void _ins(int& id,int k){
	int u,v;
	split(id,k,u,v);
	id=merge(merge(u,nnode(k)),v);
	return;
}
inline void _del(int& id,int k){
	int u,v,w;
	split(id,k,v,w);
	split(v,k-1,u,v);
	v=merge(t[v].ch[0],t[v].ch[1]);
	id=merge(u,merge(v,w));
	return;
}

void del(int x,int l,int r,int pos,int k){
	_del(seg[x],k);
	if(l==r){
		return;	
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		del((x<<1),l,mid,pos,k);
	}else{
		del((x<<1)|1,mid+1,r,pos,k);
	}
	
	return;
}
void add(int x,int l,int r,int pos,int k){
	_ins(seg[x],k);
	if(l==r){
		return;	
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		add((x<<1),l,mid,pos,k);
	}else{
		add((x<<1)|1,mid+1,r,pos,k);
	}
	
	return;
}

inline int qrnk(int x,int l,int r,int tl,int tr,int k){
	if(l>=tl&&r<=tr){ 
		return rnk(seg[x],k);
	}
	int mid=(l+r)>>1;
	if(tr<=mid){
		return qrnk((x<<1),l,mid,tl,tr,k);
	}else if(tl>mid){
		return qrnk((x<<1)|1,mid+1,r,tl,tr,k);
	}else{
		return qrnk((x<<1),l,mid,tl,tr,k)+qrnk((x<<1)|1,mid+1,r,tl,tr,k)-1;
	}
	
	return 2237;
}
inline int qkth(int tl,int tr,int k){
	int al=0,ar=100000000;
	while(al<ar){
		int mid=(al+ar+1)>>1;
		int rnkm=qrnk(1,1,n,tl,tr,mid);
		if(rnkm>k){
			ar=mid-1;
		}else{
			al=mid;
		}
	}
	
	return al;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(2238);
    cin>>n>>m;
	for(int i=1;i<=n;i++){
	    cin>>a[i];
	    amin=min(amin,a[i]);
	    amax=max(amax,a[i]);
		add(1,1,n,i,a[i]);
	}
	for(int i=1;i<=m;i++){
	    cin>>rop;
		if(rop==1){
		    cin>>rl>>rr>>rk;
			printf("%d\n",qrnk(1,1,n,rl,rr,rk));
		}else if(rop==2){
		    cin>>rl>>rr>>rk;
			printf("%d\n",qkth(rl,rr,rk));
		}else if(rop==3){
		    cin>>rpos>>rk;
			del(1,1,n,rpos,a[rpos]);
			add(1,1,n,rpos,rk);
	        amin=min(amin,a[i]);
	        amax=max(amax,a[i]);
			a[rpos]=rk;
		}else if(rop==4){
		    cin>>rl>>rr>>rk;
			int rkk=qrnk(1,1,n,rl,rr,rk);
			if(rkk==1){
				printf("-2147483647\n");
			}else{
				printf("%d\n",qkth(rl,rr,rkk-1));
			}
		}else{
		    cin>>rl>>rr>>rk;
			int rkk=qrnk(1,1,n,rl,rr,rk+1);
			if(rkk>rr-rl+1){
				printf("2147483647\n");
			}else{
				printf("%d\n",qkth(rl,rr,rkk));
			}
		}
	}
	
	return 0;
}