rt,谢谢各位大佬

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=2147483647;
const int N=2e7+5;
int key[N],siz[N],a[N],wei[N],ls[N],rs[N];
int tot;
struct Treap{
	int root;
	inline void pushup(int o) {siz[o]=siz[ls[o]]+siz[rs[o]]+1;}
	pair<int,int> spilt(int o,int k) {
		if(!o) return make_pair(0,0);
		if(key[o]<k) {
			pair<int,int> t=spilt(rs[o],k);
			rs[o]=t.first;     pushup(o);
			return make_pair(o,t.second);
		}
		else {
			pair<int,int> t=spilt(ls[o],k);
			ls[o]=t.second;   pushup(o);
			return make_pair(t.first,o);
		}
	}
	int merge(int u,int v) {
		if(!u||!v) return u+v;
		if(wei[u]<wei[v]) {
			rs[u]=merge(rs[u],v);
			pushup(u); return u;
		}
		else {
			ls[v]=merge(u,ls[v]);
			pushup(v); return v;
		}
	}
	inline void insert(int k) {
		key[++tot]=k; siz[tot]=1; wei[tot]=(rand()<<10)+rand();
		pair<int,int> t=spilt(root,k);
		root=merge(merge(t.first,tot),t.second);
	}
	inline void erase(int k) {
		pair<int,int> x,y;
		x=spilt(root,k);
		y=spilt(x.second,k+1);
		y.first=merge(ls[y.first],rs[y.first]);
		root=merge(x.first,merge(y.first,y.second));
	}
	inline int find(int k) {
		int res=0;
		pair<int,int> t=spilt(root,k);
		res=siz[t.first]+1;
		root=merge(t.first,t.second);
		return res;
	}
	inline void build(int l,int r) {for(int i=l;i<=r;i++) insert(a[i]);}
	int pre(int k) {
		pair<int,int> t=spilt(root,k);
		int p=t.first;
		if(!p) return -inf;
		while(rs[p]) p=rs[p];
		int ans=key[p];
		root=merge(t.first,t.second);
		return ans;	
	}
	int nxt(int k) {
		pair<int,int> t=spilt(root,k);
		int p=t.second;
		if(!p) return inf;
		while(ls[p]) p=ls[p];
		int ans=key[p];
		root=merge(t.first,t.second);
		return ans;
	}
};
Treap tr[N];
void build(int o,int l,int r) {
	tr[o].build(l,r);
	if(l==r) return ;
	int mid=(l+r)/2;
	build(o*2,l,mid); build(o*2+1,mid+1,r);
}
int queryrank(int o,int l,int r,int s,int t,int val) {
	if(r<s||t<l) return 0;
	if(s<=l&&r<=t) return tr[o].find(val)-1;
	int mid=(l+r)/2;
	return queryrank(o*2,l,mid,s,t,val)+queryrank(o*2+1,mid+1,r,s,t,val);
}
inline int querykey(int s,int t,int rk,int n) {
	int l=0,r=1e8,ans=-1;	
	while(l<=r) {
		int mid=(l+r)/2;
		if(queryrank(1,1,n,s,t,mid)+1<=rk) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
} 
void update(int o,int l,int r,int p,int val) {
	if(r<p||p<l) return ;
	tr[o].erase(a[p]); tr[o].insert(val);
	if(l==r) return ;	
	int mid=(l+r)/2;
	update(o*2,l,mid,p,val);	
	update(o*2+1,mid+1,r,p,val);
}
int Pre(int o,int l,int r,int s,int t,int k) {
	if(r<s||t<l) return -inf;
	if(s<=l&&r<=t) return tr[o].pre(k);
	int mid=(l+r)/2;
	return max(Pre(o*2,l,mid,s,t,k),Pre(o*2+1,mid+1,r,s,t,k));
}
int Nxt(int o,int l,int r,int s,int t,int k) {
	if(r<s||t<l) return inf;
	if(s<=l&&r<=t) return tr[o].nxt(k);
	int mid=(l+r)/2;
	return min(Nxt(o*2,l,mid,s,t,k),Nxt(o*2+1,mid+1,r,s,t,k));
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	srand(time(0));
	int n,m;
	cin>>n>>m;	
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--) {
		int opt,l,r,k,pos,ans=0;
		cin>>opt;
		if(opt==1) cin>>l>>r>>k,cout<<queryrank(1,1,n,l,r,k)+1<<'\n';
		if(opt==2) cin>>l>>r>>k,cout<<querykey(l,r,k,n)<<'\n';
		if(opt==3) cin>>pos>>k,update(1,1,n,pos,k),a[pos]=k;
		if(opt==4) cin>>l>>r>>k,cout<<Pre(1,1,n,l,r,k)<<'\n';
		if(opt==5) cin>>l>>r>>k,cout<<Nxt(1,1,n,l,r,k)<<'\n';
	}
}