神秘树套树玄关求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
const int inf=2147483647;
inline int read() {
	int x=0,f=0;
	char c=getchar();
	while(!isdigit(c)) {
		f|=c=='-';
		c=getchar();
	}
	while(isdigit(c)) {
		x=x*10+c-48;
		c=getchar();
	}
	return f?-x:x;
}
struct qst {
	int op,l,r,x;
} q[N];
inline int lb(int x) {
	return x&-x;
}
int a[N<<5],n,m,len,lsh[N<<4],rooot[N<<2];
int tot=0,num=0,cnt=0;
int tmp[N<<5],tem[N<<5];
struct tree {
	struct nod {
		int v,ls,rs;
	} w[N<<5];
	int add(int u) {
		w[++tot]=w[u];
		return tot;
	}
	void psh(int u) {
		w[u].v=w[w[u].ls].v+w[w[u].rs].v;
	}
	int chg(int u,int l,int r,int k,int x) {
		if(!u)u=add(u);
		if(l==r) {
			w[u].v=x;
			return u;
		}
		int mid=(l+r)>>1;
		if(k<=mid)w[u].ls=chg(w[u].ls,l,mid,k,x);
		else w[u].rs=chg(w[u].rs,mid+1,r,k,x);
		psh(u);
		return u;
	}
	int qry(int l,int r,int k) {
		if(l==r) {
			return l;
		}
		int mid=(l+r)>>1;
		int sum=0;
		for(int i=1; i<=cnt; i++)sum+=w[w[tem[i]].ls].v;
		for(int i=1; i<=num; i++)sum-=w[w[tmp[i]].ls].v;
		if(k<=sum) {
			for(int i=1; i<=cnt; i++)tem[i]=w[tem[i]].ls;
			for(int i=1; i<=num; i++)tmp[i]=w[tmp[i]].ls;
			return qry(l,mid,k);
		} else {
			for(int i=1; i<=cnt; i++)tem[i]=w[tem[i]].rs;
			for(int i=1; i<=num; i++)tmp[i]=w[tmp[i]].rs;
			return qry(mid+1,r,k-sum);
		}
	}
	int qry_rk(int l,int r,int k) {
		if(l==r) {
			return 0;
		}
		int mid=(l+r)>>1;
		int sum=0;
		if(k<=mid) {
			for(int i=1; i<=cnt; i++)tem[i]=w[tem[i]].ls;
			for(int i=1; i<=num; i++)tmp[i]=w[tmp[i]].ls;
			return qry(l,mid,k);
		} else {
			for(int i=1; i<=cnt; i++)sum+=w[w[tem[i]].ls].v,tem[i]=w[tem[i]].rs;
			for(int i=1; i<=num; i++)sum-=w[w[tmp[i]].ls].v,tmp[i]=w[tmp[i]].rs;
			return sum+qry(mid+1,r,k);
		}
	}

} seg;
struct Node {
	void Add(int u,int x) {
		for(int i=u; i<=n; i+=lb(i)) {
			rooot[i]=seg.chg(rooot[i],1,len,a[u],x);
		}
	}
	int fid_num(int l,int r,int k) {
		num=cnt=0;
		for(int i=r; i; i-=lb(i)) {
			tem[++cnt]=rooot[i];
		}
		for(int i=l-1; i; i-=lb(i)) {
			tmp[++num]=rooot[i];
		}

		return seg.qry(1,len,k);
	}
	int fid_rk(int l,int r,int k) {
		num=cnt=0;
		for(int i=r; i; i-=lb(i)) {
			tem[++cnt]=rooot[i];
		}
		for(int i=l-1; i; i-=lb(i)) {
			tmp[++num]=rooot[i];
		}
		return seg.qry_rk(1,len,k)+1;
	}
	int fid_pre(int l,int r,int k) {
		int rk=fid_rk(l,r,k)-1;
		if(rk==0)return 0;
		return fid_num(l,r,rk);
	}
	int fid_bck(int l,int r,int k) {
		if(k==len)return len+1;
		int rk=fid_rk(l,r,k+1);
		if(rk==r-l+2)return len+1;
		return fid_num(l,r,rk);
	}
} tre;
signed main() {
	n=read(),m=read();
	for(int i=1; i<=n; i++) {
		lsh[++len]=a[i]=read();
	}
	for(int i=1; i<=m; i++) {
		q[i].op=read();
		q[i].l=read();
		q[i].r=read();
		if(q[i].op!=3) q[i].x=read();
		else lsh[++len]=q[i].r;
		if(q[i].op==4 || q[i].op==5) lsh[++len]=q[i].x;
	}
	sort(lsh+1,lsh+1+len);
	len=unique(lsh+1,lsh+1+len)-lsh-1;
	lsh[0]=-inf,lsh[len+1]=inf;
	for(int i=1; i<=n; i++) {
		a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;
		tre.Add(i,1);
	}
	for(int i=1; i<=m; i++) {
		if(q[i].op==3) {
			tre.Add(q[i].l,-1);
			a[q[i].l]=lower_bound(lsh+1,lsh+1+len,q[i].r)-lsh;
			tre.Add(q[i].l,1);
		}
		if(q[i].op==1) {
			q[i].x=lower_bound(lsh+1,lsh+1+len,q[i].x)-lsh;
			printf("%lld\n",tre.fid_rk(q[i].l,q[i].r,q[i].x));
		}
		if(q[i].op==2) {
			printf("%lld\n",lsh[tre.fid_num(q[i].l,q[i].r,q[i].x)]);
		}
		if(q[i].op==4) {
			printf("%lld\n",lsh[tre.fid_pre(q[i].l,q[i].r,lower_bound(lsh+1,lsh+1+len,q[i].x)-lsh)]);
		}
		if(q[i].op==5) {
			printf("%lld\n",lsh[tre.fid_bck(q[i].l,q[i].r,lower_bound(lsh+1,lsh+1+len,q[i].x)-lsh)]);
		}
	}
}