RT，卡常卡吐了， $90$ 分TLE#2求助。

#include<bits/stdc++.h>
#define fir 1,1,n
#define seg int p,int l,int r
#define mid (l+r>>1)
#define lid p<<1,l,mid
#define rid p<<1|1,mid+1,r
#define lsiz tr[tr[p].l].siz
#define rsiz tr[tr[p].r].siz 
inline void read(int &x){
	x=0;int f=1;char s=getchar();
	for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
	for(;s>='0'&&s<='9';s=getchar()) x=(x<<3)+(x<<1)+s-48;
	x*=f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
const int N=5e4+5,Inf=2147483647;
struct treap{int siz,s,hp,l,r;}tr[N*200];
int rt[N<<2],n,m,a[N],trt;
int get_new(int v){tr[++trt]=(treap){1,v,rand(),0,0};return trt;}
void trp_he(int &p,int x,int y){
	if(!x||!y){p=x+y;return;}
	if(tr[x].hp<tr[y].hp) trp_he(tr[p=x].r,tr[x].r,y);
	else trp_he(tr[p=y].l,x,tr[y].l);
	tr[p].siz=lsiz+rsiz+1;
}
void trp_lie(int p,int &x,int &y,int v){
	if(!p){x=y=0;return;}
	if(tr[p].s<=v) trp_lie(tr[x=p].r,tr[p].r,y,v);
	else trp_lie(tr[y=p].l,x,tr[p].l,v);
	tr[p].siz=lsiz+rsiz+1;
}
int askkth(int p,int k){
	if(!p)return -1;
	if(lsiz+1==k)return tr[p].s;
	if(lsiz>=k)return askkth(tr[p].l,k);
	return askkth(tr[p].r,k-lsiz-1);
}
void trp_add(int &p,int v){
	int x,y;
	trp_lie(p,x,y,v);
	trp_he(x,x,get_new(v)),trp_he(p,x,y);
}
void trp_del(int &p,int v){
	int x,y,z;
	trp_lie(p,x,y,v-1),trp_lie(y,z,y,v);
	trp_he(z,tr[z].l,tr[z].r);
	trp_he(y,z,y),trp_he(p,x,y);
} 
int trp_ask_rk(int p,int k){
	int x,y;
	trp_lie(p,x,y,k-1);
	int ans=tr[x].siz;
	trp_he(p,x,y);
	return ans;
}
int trp_las(int p,int k){
	int x,y;
	trp_lie(p,x,y,k-1);
	int ans=askkth(x,tr[x].siz);
	trp_he(p,x,y);
	return ans>=0?ans:-Inf;
}
int trp_nex(int p,int k){
	int x,y;
	trp_lie(p,x,y,k);
	int ans=askkth(y,1);
	trp_he(p,x,y);
	return ans>=0?ans:Inf;
}
void seg_build(seg){
	for(int i=l;i<=r;i++)trp_add(rt[p],a[i]);
	if(l==r)return;
	seg_build(lid),seg_build(rid);
}
int seg_ask_rk(seg,int L,int R,int k){
	if(L<=l&&R>=r)return trp_ask_rk(rt[p],k);
	return (L<=mid?seg_ask_rk(lid,L,R,k):0)+(R>mid?seg_ask_rk(rid,L,R,k):0);
}
int seg_ask_val(int L,int R,int k){
	int l=0,r=1e8+5,ans=0;
	while(l<=r){
		if(seg_ask_rk(fir,L,R,mid)+1<=k)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
void seg_change(seg,int x,int y){
	trp_del(rt[p],a[x]),trp_add(rt[p],y);
	if(l==r)return;
	if(x<=mid) seg_change(lid,x,y);
	else seg_change(rid,x,y);
}
int seg_ask_las(seg,int L,int R,int k){
	if(L<=l&&R>=r)return trp_las(rt[p],k);
	return Max((L<=mid?seg_ask_las(lid,L,R,k):-Inf),(R>mid?seg_ask_las(rid,L,R,k):-Inf));
}
int seg_ask_nex(seg,int L,int R,int k){
	if(L<=l&&R>=r)return trp_nex(rt[p],k);
	return Min((L<=mid?seg_ask_nex(lid,L,R,k):Inf),(R>mid?seg_ask_nex(rid,L,R,k):Inf));
}
int main(){
	srand(time(0));
	read(n),read(m);
	for(int i=1;i<=n;i++)read(a[i]);
	seg_build(fir);
	for(int i=1;i<=m;i++){
		int T,l,r,k,x,y;
		read(T);
		if(T==1){
			read(l),read(r),read(k);
			write(seg_ask_rk(fir,l,r,k)+1),puts("");
		}
		if(T==2){
			read(l),read(r),read(k);
			write(seg_ask_val(l,r,k)),puts("");
		}
		if(T==3){
			read(x),read(y);
			seg_change(fir,x,y);
			a[x]=y;
		}
		if(T==4){
			read(l),read(r),read(k); 
			write(seg_ask_las(fir,l,r,k)),puts("");
		}
		if(T==5){
			read(l),read(r),read(k);
			write(seg_ask_nex(fir,l,r,k)),puts("");
		}
	}
}