RT，#2不开O2TLE，开了跑得飞快，求dalao指点一下

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
const int N = 2e5 + 1;
const int inf = 2147483647;
const double alpha = 0.75;
#define mid (l + r >> 1)
int n,m,a[N],rt[N],buc[N],tot,num;
struct yjx{
	int ls[N * 30],rs[N * 30],val[N * 30],cnt[N * 30],siz[N * 30];
	inline void pushup(int k){
		siz[k] = siz[ls[k]] + siz[rs[k]] + cnt[k];
	}
	inline bool unb(int k){
		return alpha * siz[k] < max(siz[ls[k]],siz[rs[k]]);
	}
	void extract(int k){
		if(ls[k]) extract(ls[k]);
		if(cnt[k]) buc[++num] = k;
		if(rs[k]) extract(rs[k]);
	}
	void build(int &k,int l,int r){
		if(l > r){
			k = 0;
			return;
		}
		k = buc[mid];
		build(ls[k],l,mid - 1);
		build(rs[k],mid + 1,r);
		pushup(k);
	}
	inline void rebuild(int &k){
		num = 0;
		extract(k);
		build(k,1,num);
	}
	void insert(int &k,int c){
		if(!k){
			k = ++tot;
			ls[k] = rs[k] = 0;
			val[k] = c;
			siz[k] = cnt[k] = 1;
			return;
		}
		if(val[k] == c){
			++cnt[k];
			pushup(k);
			return;
		}
		if(c < val[k]) insert(ls[k],c);
		else insert(rs[k],c);
		pushup(k);
		if(unb(k)) rebuild(k);
	}
	void del(int &k,int c){
		if(c == val[k]){
			--cnt[k];
			pushup(k);
			return;
		}
		if(c < val[k]) del(ls[k],c);
		else del(rs[k],c);
		pushup(k);
		if(unb(k)) rebuild(k);
	}
	void print(int k){
		if(ls[k]) print(ls[k]);
		printf("%d ",val[k]);
		if(rs[k]) print(rs[k]);
	}
	inline int query_rnk(int k,int c){
		int ret = 1;
		while(1){
			if(!k) return ret;
			if(c == val[k]) return ret + siz[ls[k]];
			if(c < val[k]){
				k = ls[k];
			}
			else{
				ret += siz[ls[k]] + cnt[k];
				k = rs[k];
			}
		}
	}
	inline int query_kth(int k,int c){
		while(1){
			if(!k){
				if(!c) return -inf;
				else return inf;
			}
			if(c > siz[ls[k]] && c <= siz[ls[k]] + cnt[k]) return val[k];
			if(c <= siz[ls[k]]){
				k = ls[k];
			}
			else{
				c -= siz[ls[k]] + cnt[k];
				k = rs[k];
			}
		}
	}
	inline int query_pre(int k,int c){
		int temp = query_rnk(k,c) - 1;
		return query_kth(k,temp);
	}
	inline int query_nxt(int k,int c){
		int temp = query_rnk(k,c + 1);
		return query_kth(k,temp);
	}
}bt;
struct wyx{
	void build(int k,int l,int r){
		for(int i = l;i <= r;i++) bt.insert(rt[k],a[i]);
		if(l == r) return;
		build(k << 1,l,mid);
		build(k << 1 | 1,mid + 1,r);
	}
	void modify(int k,int l,int r,int x,int c){
		bt.del(rt[k],a[x]);
		bt.insert(rt[k],c);
		if(l == r) return;
		if(x <= mid) modify(k << 1,l,mid,x,c);
		else modify(k << 1 | 1,mid + 1,r,x,c);
	}
	int query_rnk(int k,int l,int r,int x,int y,int c){
		if(x <= l && r <= y){
			return bt.query_rnk(rt[k],c);
		}
		int ret = 0;
		if(x <= mid) ret += query_rnk(k << 1,l,mid,x,y,c);
		if(y > mid) ret += query_rnk(k << 1 | 1,mid + 1,r,x,y,c);
		if(x <= mid && y > mid) --ret;
		return ret;
	}
	int query_kth(int x,int y,int c){
		int l = 0,r = 1e8;
		while(l < r){
			int Mid = (l + r + 1) >> 1;
			if(query_rnk(1,1,n,x,y,Mid) > c) r = Mid - 1;
			else l = Mid;
		}
		return l;
	}
	int query_pre(int k,int l,int r,int x,int y,int c){
		if(x <= l && r <= y){
			return bt.query_pre(rt[k],c);
		}
		int ret = -inf;
		if(x <= mid) ret = query_pre(k << 1,l,mid,x,y,c);
		if(y > mid) ret = max(ret,query_pre(k << 1 | 1,mid + 1,r,x,y,c));
		return ret;
	}
	int query_nxt(int k,int l,int r,int x,int y,int c){
		if(x <= l && r <= y){
			return bt.query_nxt(rt[k],c);
		}
		int ret = inf;
		if(x <= mid) ret = query_nxt(k << 1,l,mid,x,y,c);
		if(y > mid) ret = min(ret,query_nxt(k << 1 | 1,mid + 1,r,x,y,c));
		return ret;
	}
}str;
int main(){
	int i,x,y,w,opt;
	n = read(),m = read();
	for(i = 1;i <= n;i++){
		a[i] = read();
	}
	str.build(1,1,n);
	for(i = 1;i <= m;i++){
		opt = read();
		if(opt == 1){
			x = read(),y = read(),w = read();
			printf("%d\n",str.query_rnk(1,1,n,x,y,w));
		}
		if(opt == 2){
			x = read(),y = read(),w = read();
			printf("%d\n",str.query_kth(x,y,w));
		}
		if(opt == 3){
			x = read(),w = read();
			str.modify(1,1,n,x,w);
			a[x] = w;
		}
		if(opt == 4){
			x = read(),y = read(),w = read();
			printf("%d\n",str.query_pre(1,1,n,x,y,w));
		}
		if(opt == 5){
			x = read(),y = read(),w = read();
			printf("%d\n",str.query_nxt(1,1,n,x,y,w));
		}
	}
	return 0;
}