RT，是我人傻常数大吗？\kk

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define pfor(i,x,y) for(register int i=x;i<=y;++i)
#define mfor(i,x,y) for(register int i=x;i>=y;--i)
constexpr inline int maxx(const int &x,const int &y){return x>y?x:y;}
constexpr inline int minx(const int &x,const int &y){return x<y?x:y;}
constexpr inline int absx(const int &x){return (x>0)?(x):(~x+1);}
inline int read(){
	int x=0;bool flag=false;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') flag=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return flag?~x+1:x;
}
inline void write(int x){
	if(x<0){putchar('-');x=(~x+1);}
	if(x/10) write(x/10);
	putchar((x%10)^48);
	return;
}
const int N=1e7+5;
int n,m,a[N],opt,x,y,z;
struct TreapNode{int lch,rch,data,rank,size,cnt;};
struct treap{
	int root,tot,q;
	TreapNode t[N];
	inline int New(int x){
		t[++tot].data=x,t[tot].rank=rand();
		t[tot].size=t[tot].cnt=1;
		return tot;
	}
	inline void pushup(int p){
		t[p].size=t[t[p].lch].size+t[t[p].rch].size+t[p].cnt;
		return;
	}
	inline void zig(int &p){
		q=t[p].lch,t[p].lch=t[q].rch,t[q].rch=p;
		pushup(p),pushup(q);p=q;
		return;
	}
	inline void zag(int &p){
		q=t[p].rch,t[p].rch=t[q].lch,t[q].lch=p;
		pushup(p),pushup(q);p=q;
		return;
	}
	inline void build(){
		t[root=New(-INT_MAX)].rch=New(INT_MAX);
		pushup(root);
		if(t[root].rank<t[t[root].rch].rank) zag(root);
		return;
	}
	inline void insert(int &p,int x){
		if(!p) p=New(x);
		else if(t[p].data==x) ++t[p].cnt;
		else{
			if(x<t[p].data){
				insert(t[p].lch,x);
				if(t[p].rank<t[t[p].lch].rank) zig(p);
			}
			else{
				insert(t[p].rch,x);
				if(t[p].rank<t[t[p].rch].rank) zag(p);
			}
		}
		pushup(p);
		return;
	}
	inline void erase(int &p,int x){
		if(t[p].data==x){
			if(t[p].cnt>1) --t[p].cnt;
			else if(t[p].lch||t[p].rch){
				if(!t[p].rch||t[t[p].lch].rank>t[t[p].rch].rank)
					zig(p),erase(t[p].rch,x);
				else zag(p),erase(t[p].lch,x);
			}
			else p=0;
		}
		else if(x<t[p].data) erase(t[p].lch,x);
		else erase(t[p].rch,x);
		pushup(p);
		return;
	}
	inline int getrank(int p,int x){
		if(!p) return 0;
		if(x<t[p].data) return getrank(t[p].lch,x);
		if(x==t[p].data) return t[t[p].lch].size;
		return t[t[p].lch].size+t[p].cnt+getrank(t[p].rch,x);
	}
	inline int getdata(int p,int x){
		if(t[t[p].lch].size>=x) return getdata(t[p].lch,x);
		if(t[t[p].lch].size+t[p].cnt>=x) return t[p].data;
		return getdata(t[p].rch,x-t[t[p].lch].size-t[p].cnt);
	}
	inline int getpre(int p,int x){
		if(!p) return -INT_MAX;
		if(t[p].data>=x) return getpre(t[p].lch,x);
		return maxx(t[p].data,getpre(t[p].rch,x));
	}
	inline int getnxt(int p,int x){
		if(!p) return INT_MAX;
		if(t[p].data<=x) return getnxt(t[p].rch,x);
		return minx(t[p].data,getnxt(t[p].lch,x));
	}
}treap;
struct SegmentTreeNode{int l,r,root;};
struct SegmentTree{
	SegmentTreeNode t[N<<2];
	inline void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		pfor(i,l,r) treap.insert(t[p].root,a[i]);
		if(l==r) return;
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		return;
	}
	inline int getrank(int p,int l,int r,int x){
		if(l<=t[p].l&&t[p].r<=r) return treap.getrank(t[p].root,x);
		int mid=t[p].l+t[p].r>>1,res=0;
		if(l<=mid) res+=getrank(p<<1,l,r,x);
		if(r>mid) res+=getrank(p<<1|1,l,r,x);
		return res;
	}
	inline void change(int p,int q,int x){
		treap.erase(t[p].root,a[q]);
		treap.insert(t[p].root,x);
		if(t[p].l==t[p].r) return;
		int mid=t[p].l+t[p].r>>1;
		if(q<=mid) change(p<<1,q,x);
		if(q>mid) change(p<<1|1,q,x);
		return;
	}
	inline int getpre(int p,int l,int r,int x){
		if(l<=t[p].l&&t[p].r<=r) return treap.getpre(t[p].root,x);
		int mid=t[p].l+t[p].r>>1,res=-INT_MAX;
		if(l<=mid) res=maxx(res,getpre(p<<1,l,r,x));
		if(r>mid) res=maxx(res,getpre(p<<1|1,l,r,x));
		return res;
	}
	inline int getnxt(int p,int l,int r,int x){
		if(l<=t[p].l&&t[p].r<=r) return treap.getnxt(t[p].root,x);
		int mid=t[p].l+t[p].r>>1,res=INT_MAX;
		if(l<=mid) res=minx(res,getnxt(p<<1,l,r,x));
		if(r>mid) res=minx(res,getnxt(p<<1|1,l,r,x));
		return res;
	}
	inline int getdata(int l,int r,int k){
		int ll=0,rr=1e8+1;
		while(ll<rr){
			int mid=ll+rr+1>>1;
			if(getrank(1,l,r,mid)<k) ll=mid;
			else rr=mid-1;
		}
		return rr;
	}
}tree;
signed main(){
	n=read(),m=read();
	pfor(i,1,n) a[i]=read();
	tree.build(1,1,n);
	while(m--){
		opt=read();
		if(opt==1){
			x=read(),y=read(),z=read();
			write(tree.getrank(1,x,y,z)+1),puts("");
		}
		else if(opt==2){
			x=read(),y=read(),z=read();
			write(tree.getdata(x,y,z)),puts("");
		}
		else if(opt==3){
			x=read(),y=read();
			tree.change(1,x,y);a[x]=y;
		}
		else if(opt==4){
			x=read(),y=read(),z=read();
			write(tree.getpre(1,x,y,z)),puts("");
		}
		else if(opt==5){
			x=read(),y=read(),z=read();
			write(tree.getnxt(1,x,y,z)),puts("");
		}
	}
	return 0;
}