代码可能有点丑，一楼附上chatgpt优化版。hack数据在最后

求求大佬了，orz
^_^

//树套树 
#include<bits/stdc++.h>
using namespace std;
#define lc (u<<1)
#define rc (u<<1|1)
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define inf 0x7fffffff
#define N 500009 
#define auto int
inline auto read(){
	auto x=0,f=1;
	auto c='\0';
	for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
class node{
public:
	int s[2],fa,val,size;
	node()=default;
	void init(int p,int v){fa=p,val=v,size=1;}
}tr[N*40];
//unordered_map<int,int>w,root;
//unordered_map<int,node>tr;
int w[N],root[N];
int n,m,idx,op,x,l,r,pos,k;
inline void pushup(auto x){
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
} 
inline void rotate(auto x){//旋转※包括左旋和右旋 
	auto y=tr[x].fa,z=tr[y].fa;//y=father;z=grandfather
	auto k=tr[y].s[1]==x;//k=x is y's which son
	tr[y].s[k]=tr[x].s[k^1];
	tr[tr[x].s[k^1]].fa=y;
	tr[x].s[k^1]=y;
	tr[y].fa=x;
	tr[z].s[tr[z].s[1]==y]=x;
	tr[x].fa=z;
	pushup(y),pushup(x); 
}
inline void splay(auto &root,auto x,auto k){//伸展※核心 （目标：使x成为k的儿子） 
	while(tr[x].fa!=k){
		auto y=tr[x].fa,z=tr[y].fa;
		if(z!=k)
			if((tr[y].s[0]==x&&tr[y].s[0]!=y)||(tr[y].s[0]!=x&&tr[y].s[0]==y))rotate(x);
			else rotate(y);
		rotate(x);
	}
	if(k==0)root=x; 
}
void insert(auto &root,auto v){
	auto u=root,p=0;
	while(u)p=u,u=tr[u].s[v>tr[u].val];
	u=++idx;
	tr[p].s[v>tr[p].val]=u;
	tr[u].init(p,v);
	splay(root,u,0);
}
void build(auto u,auto l,auto r){
	insert(root[u],-inf),insert(root[u],inf);
	for(int i=l;i<=r;i++)insert(root[u],w[i]);
	if(l==r)return;
	auto mid=(l+r)>>1; 
	build(lc,l,mid),build(rc,mid+1,r);
}
auto getrank(int root,int v){
	auto u=root,ret=0;
	while(u){
		if(tr[u].val<v)ret+=tr[ls(u)].size+1,u=rs(u);
		else u=ls(u); 
	}return ret;
}
auto queryrank(auto u,int l,int r,auto x,auto y,int v){
	if(x<=l&&r<=y)return getrank(root[u],v)-1;
	auto mid=(l+r)>>1,ret=0;
	if(x<=mid)ret+=queryrank(lc,l,mid,x,y,v);
	if(y>mid)ret+=queryrank(rc,mid+1,r,x,y,v);
	return ret;
}
auto queryval(auto u,auto x,auto y,auto k){
	auto l=0,r=inf,ans=0;
	while(l<=r){
		auto mid=(l+r)>>1;
		if(queryrank(1,1,n,x,y,mid)+1<=k)l=mid+1,ans=mid;
		else r=mid-1;
	}return ans;
}
void del(auto &root,auto v){
	auto u=root;
	while(u){
		if(tr[u].val==v)break;
		if(tr[u].val<v)u=rs(u);
		else u=ls(u);
	}
	splay(root,u,0);
	auto l=ls(u),r=rs(u);
	while(rs(l))l=rs(l);
	while(ls(r))r=ls(r);
	splay(root,l,0);
	splay(root,r,l);
	ls(r)=0;
	splay(root,r,0); 
}
void change(auto u,auto l,auto r,auto pos,auto v){
	del(root[u],w[pos]);
	insert(root[u],v);
	if(l==r)return;
	auto mid=(l+r)>>1;
	if(pos<=mid)change(lc,l,mid,pos,v);
	else change(rc,mid+1,r,pos,v);
}
auto getpre(auto root,auto v){
	auto u=root,ret=-inf;
	while(u){
		if(tr[u].val<v)ret=tr[u].val,u=rs(u);
		else u=ls(u);
	}return ret;
}
auto querypre(auto u,auto l,auto r,auto x,auto y,auto v){
	if(x<=l&&r<=y)return getpre(root[u],v);
	auto mid=(l+r)>>1,ret=-inf;
	if(x<=mid)ret=max(ret,querypre(lc,l,mid,x,y,v));
	if(y>mid)ret=max(ret,querypre(rc,mid+1,r,x,y,v));
	return ret;
}
auto getnxt(auto root,auto v){
	auto u=root,ret=inf;
	while(u){
		if(tr[u].val>v)ret=tr[u].val,u=ls(u);
		else u=rs(u);
	}return ret;
}
auto querynxt(auto u,auto l,auto r,auto x,auto y,auto v){
	if(x<=l&&r<=y)return getnxt(root[u],v);
	auto mid=(l+r)>>1,ret=inf;
	if(x<=mid)ret=min(ret,querynxt(lc,l,mid,x,y,v));
	if(y>mid)ret=min(ret,querynxt(rc,mid+1,r,x,y,v));
	return ret;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)w[i]=read();
	build(1,1,n);
	while(m--){
		op=read();
		switch(op){
			case 1:l=read(),r=read(),k=read(),printf("%lld\n",queryrank(1,1,n,l,r,k)+1);break;
			case 2:l=read(),r=read(),k=read(),printf("%lld\n",queryval(1,l,r,k));break;
			case 3:pos=read(),k=read(),change(1,1,n,pos,k);w[pos]=k;break;
			case 4:l=read(),r=read(),k=read(),printf("%lld\n",querypre(1,1,n,l,r,k));break;
            case 5:l=read(),r=read(),k=read(),printf("%lld\n",querynxt(1,1,n,l,r,k));break;
            default:throw("ERROR! Read the wrong op!");
		}
	}
}

对于所有的操作4，若找不到应当输出-inf(-2147483647)，但我的代码输出了+inf(2147483647)，求调。

附hack数据：

.in:
10 10
41 36 49 36 5 23 6 11 26 30 
5 2 6 11
2 7 10 2
4 7 10 50
5 8 10 4
3 2 6
5 7 7 39
5 2 7 24
5 2 5 16
4 3 6 2
1 6 6 2
.ans:
23
11
30
11
2147483647
36
36
-2147483647
1
.out:
23
11
30
11
2147483647
36
36
2147483647
1