rt，这是我的代码：

#include<bits/stdc++.h>
#define N 10000005
using namespace std;
mt19937 rnd(time(0));
int cnt,n,m,a[N],rt[N],inf=2147483647;
struct FHQ{
	int key[N],val[N],siz[N],ch[N][2];
	FHQ(){
		memset(key,0,sizeof(key));
		memset(val,0,sizeof(val));
		memset(siz,0,sizeof(siz));
		memset(ch,0,sizeof(ch));
	}
	void pushup(int x){
		siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
	}
	void split(int now,int k,int &x,int &y){
		if(!now)x=y=0;
		else{
			if(val[now]<=k)x=now,split(ch[now][1],k,ch[now][1],y);
			else y=now,split(ch[now][0],k,x,ch[now][0]);
			pushup(now);
		}
	} 
	int merge(int x,int y){
		if(!x||!y)return x+y;
		if(key[x]<key[y]){
			ch[x][1]=merge(ch[x][1],y);pushup(x);return x;
		}
		else{
			ch[y][0]=merge(x,ch[y][0]);pushup(y);return y;
		}
	}
	void insert(int w,int v){
		val[++cnt]=v;key[cnt]=rnd();siz[cnt]=1;
		int x,y;split(rt[w],v,x,y);
		rt[w]=merge(merge(x,cnt),y);
	}
	void erase(int w,int v){
		int x,y,z;
		split(rt[w],v,x,z);split(x,v-1,x,y);
		y=merge(ch[y][0],ch[y][1]);
		rt[w]=merge(x,merge(y,z));
	}
	int rnk(int w,int v){
		int x,y;split(rt[w],v-1,x,y);
		int ans=siz[x]+1;
		rt[w]=merge(x,y);
		return ans;
	}
	int find(int u,int v){
		if(v==siz[ch[u][0]]+1)return val[u];
		if(v<=siz[ch[u][0]])return find(ch[u][0],v);
		else return find(ch[u][1],v-siz[ch[u][0]]-1);
	}
	int lst(int w,int v){
		int x,y,ans;split(rt[w],v-1,x,y);
		if(siz[x])ans=find(x,siz[x]);
		else ans=-inf;
		rt[w]=merge(x,y);return ans;
	}
	int nxt(int w,int v){
		int x,y,ans;split(rt[w],v-1,x,y);
		if(siz[y])ans=find(y,1);
		else ans=inf;
		rt[w]=merge(x,y);return ans;
	}
}A;
struct Seg{
	void build(int x,int l,int r){
		for(int i=l;i<=r;++i)A.insert(x,a[i]);
		if(l==r)return;
		int mid=(l+r)>>1;
		build(x*2,l,mid);build(x*2+1,mid+1,r);
	}
	void update(int x,int l,int r,int k,int v){
		A.erase(x,a[k]);A.insert(x,v);
		if(l==r)return;
		int mid=(l+r)>>1;
		if(k<=mid)update(x*2,l,mid,k,v);
		else update(x*2+1,mid+1,r,k,v);
	}
	int rank(int x,int l,int r,int ql,int qr,int k){
		if(ql>r||qr<l)return 0;
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return A.rnk(x,k)-1;
		else return rank(x*2,l,mid,ql,qr,k)+rank(x*2+1,mid+1,r,ql,qr,k);
	}
	int num(int ql,int qr,int k){
		int l=0,r=1e8,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(rank(1,1,n,ql,qr,mid)+1<=k)l=mid+1,ans=mid;
			else r=mid-1;
		}
		return ans;
	}
	int pre(int x,int l,int r,int ql,int qr,int k){
		if(ql>r||qr<l)return -inf;
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return A.lst(x,k);
		else return max(pre(x*2,l,mid,ql,qr,k),pre(x*2+1,mid+1,r,ql,qr,k));
	}
	int suf(int x,int l,int r,int ql,int qr,int k){
		if(ql>r||qr<l)return inf;
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return A.nxt(x,k);
		else return min(suf(x*2,l,mid,ql,qr,k),suf(x*2+1,mid+1,r,ql,qr,k));
	}
}S; 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>a[i];
	S.build(1,1,n);
	while(m--){
		int op,l,r,k;cin>>op>>l>>r;
		if(op!=3)cin>>k;
		if(op==1)cout<<S.rank(1,1,n,l,r,k)+1<<'\n';
		else if(op==2)cout<<S.num(l,r,k)<<'\n';
		else if(op==3)S.update(1,1,n,l,r),a[l]=r;
		else if(op==4)cout<<S.pre(1,1,n,l,r,k)<<'\n';
		else cout<<S.suf(1,1,n,l,r,k)<<'\n';
	}
	return 0;
}