GG-526互联

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ls t[x].l
#define rs t[x].r
using namespace std;

const int N=5e4+10;
const int mod=1e9+7;
const int inf=2147483647;

int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>=48&&ch<=57) {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

int a[N];
int rt,tot=0;
struct Spl {
	int val,cnt,siz;
	int fa,l,r;
} t[N];
	
struct SPL {

	int newnode(int x,int y) {
		t[++tot].fa=y;
		t[tot].siz=t[tot].cnt=1;
		t[tot].val=x;
		return tot;
	}

	void to_clear(int x) {
		t[x].fa=t[x].val=t[x].siz=t[x].cnt=t[x].l=t[x].r=0;
	}

	void push_up(int x) {
		to_clear(0);
		t[x].siz=t[x].cnt+t[ls].siz+t[rs].siz;
	}

	void rotate(int x) {

		int f1=t[x].fa;
		int f2=t[f1].fa;
		if(f2) {
			if(t[f2].l==f1) t[f2].l=x;
			else t[f2].r=x;
		}
		t[x].fa=f2;
		t[f1].fa=x;
		if(t[f1].l==x) t[f1].l=rs,t[rs].fa=f1,rs=f1;
		else t[f1].r=ls,t[ls].fa=f1,ls=f1;
		push_up(f1);
		push_up(x);

	}

	void splay(int x) {

		while(t[x].fa) {

			int f1=t[x].fa;
			int f2=t[f1].fa;
			if(f2) {
				if((t[f1].l==x)^t[f2].l==f1) rotate(x);
				else rotate(f1);
			}
			rotate(x);

		}
		rt=x;

	}

	void insert(int &x,int y,int fa) {

		if(!x) {
			x=newnode(y,fa);
			splay(x);
			return ;
		}
		if(t[x].val==y) {
			t[x].cnt++;
			t[x].siz++;
			return ;
		}
		if(y>t[x].val) insert(rs,y,x);
		else insert(ls,y,x);
		push_up(x);

	}

	int get_rk(int x,int y) {

		if(!x) return 0;
		int rk=t[ls].siz;
		if(t[x].val==y) {
			splay(x);
			return rk+1;
		} 
		if(y>t[x].val) return get_rk(rs,y)+rk+t[x].cnt;
		else return get_rk(ls,y);

	}

	int get_val(int x,int y) {

		if(y>t[ls].siz&&y<=t[ls].siz+t[x].cnt) return t[x].val;
		if(y<=t[ls].siz) return get_val(ls,y);
		else return get_val(rs,y-(t[ls].siz+t[x].cnt));

	}

	int get_nxt(int x,int y) {

		if(!x) return inf;
		if(y<t[x].val) return min(t[x].val,get_nxt(ls,y));
		else return get_nxt(rs,y);

	}

	int get_pre(int x,int y) {

		if(!x) return -inf;
		if(y>t[x].val) return max(t[x].val,get_pre(rs,y));
		else return get_pre(ls,y);

	}

	void del(int x) {

		int rk=get_rk(rt,x);
		rk=rt;
		t[rk].cnt--;
		if(t[rk].cnt) return ;
		if(!t[rk].l&&!t[rk].r) to_clear(rk),rk=rt=0;
		else if(!t[rk].l) rt=t[rk].r,t[rt].fa=0,to_clear(rk);
		else if(!t[rk].r) rt=t[rk].l,t[rt].fa=0,to_clear(rk);
		else {
			
			int p=t[rk].l;
			while(t[p].r) p=t[p].r;
			splay(p);
			t[p].r=t[rk].r;
			t[t[rk].r].fa=p;
			to_clear(rk);
			
		}
		push_up(rt);

	}


} p[N<<2];

int lc(int x) {
	return x<<1;
}
int rc(int x) {
	return x<<1|1;
}
int n,m;
struct SEG{

	void build(int o,int l,int r) {

		for(int i=l;i<=r;i++) {
			p[o].insert(o,a[i],0);
		}
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(lc(o),l,mid);
		build(rc(o),mid+1,r);

	}

	void upd(int o,int l,int r,int x,int k) {
		
		p[o].del(a[x]);
		p[o].insert(o,k,0);
		if(l==r) return ;
		int mid=(l+r)>>1;
		upd(lc(o),l,mid,x,k);
		upd(rc(o),mid+1,r,x,k);

	}

	int qry_rk(int o,int l,int r,int x,int y,int k) {

		int RK=0;
		if(x<=l&&r<=y) {
			return p[o].get_rk(o,k)-1;
		}
		int mid=(l+r)>>1;
		if(x<=mid) RK+=qry_rk(lc(o),l,mid,x,y,k);
		if(y>mid) RK+=qry_rk(rc(o),mid+1,r,x,y,k);
		return RK;

	}

	int qry_val(int x,int y,int k) {

		int l=0,r=inf,val=-1;
		while(l<=r) {

			int mid=(l+r)>>1;
			if(qry_rk(1,1,n,x,y,mid)+1<=k) {
				l=mid;
				val=mid+1;
			} else {
				r=mid-1;
			}

		}
		return val;

	}

	int qry_pre(int o,int l,int r,int x,int y,int k) {

		int pre=-inf;
		if(x<=l&&r<=y) {
			return p[o].get_pre(o,k);
		}
		int mid=(l+r)>>1;
		if(x<=mid) pre=max(qry_rk(lc(o),l,mid,x,y,k),pre);
		if(y>mid) pre=max(qry_rk(rc(o),mid+1,r,x,y,k),pre);
		return pre;

	}

	int qry_nxt(int o,int l,int r,int x,int y,int k) {

		int nxt=inf;
		if(x<=l&&r<=y) {
			return p[o].get_nxt(o,k);
		}
		int mid=(l+r)>>1;
		if(x<=mid) nxt=min(qry_rk(lc(o),l,mid,x,y,k),nxt);
		if(y>mid) nxt=min(qry_rk(rc(o),mid+1,r,x,y,k),nxt);
		return nxt;

	}
	
} T;

int op,l,r,k;

signed main() {

	n=read();
	m=read();
	for(int i=1;i<=n;i++) {
		a[i]=read();
	}
	T.build(1,1,n);

	while(m--) {

		op=read();
		if(op==1) {
			l=read();
			r=read();
			k=read();
			printf("%d\n",T.qry_rk(1,1,n,l,r,k));
		} else if(op==2) {
			l=read();
			r=read();
			k=read();
			printf("%d\n",T.qry_val(l,r,k));
		} else if(op==3) {
			l=read();
			k=read();
			T.upd(1,1,n,l,k);
		} else if(op==4){
			l=read();
			r=read();
			k=read();
			printf("%d\n",T.qry_pre(1,1,n,l,r,k));
		} else {
			l=read();
			r=read();
			k=read();
			printf("%d\n",T.qry_nxt(1,1,n,l,r,k));
		}

	}

	return 0;
}