RT

我根本不会二分。

#include<bits/stdc++.h>
#include<random>
using namespace std;
typedef long long ll;
mt19937 rd(time(0));
const ll MAXN=5e5+5;
ll n,m,op,x,y,z;
ll a[MAXN];
struct node{
	ll lson,rson;
	ll val,pri,sz;
};
node treap[MAXN*20];
ll tot,rt[MAXN];
void new_node(ll num){
	tot++;
	treap[tot].val=num;
	treap[tot].pri=rd();
	treap[tot].lson=treap[tot].rson=0;
	treap[tot].sz=1;
	return;
}
void update(ll now){
	treap[now].sz=treap[treap[now].lson].sz+treap[treap[now].rson].sz+1;
	return;
}
void split(ll now,ll num,ll &L,ll &R){
	if(now==0){
		L=R=0;
		return;
	}
	if(treap[now].val<=num){
		L=now;
		split(treap[now].rson,num,treap[now].rson,R);
	}
	else{
		R=now;
		split(treap[now].lson,num,L,treap[now].lson); 
	}
	update(now);
	return;
}
ll merge(ll L,ll R){
	if(L==0||R==0)return L+R;
	if(treap[L].pri>treap[R].pri){
		treap[L].rson=merge(treap[L].rson,R);
		update(L);
		return L;
	}
	else{
		treap[R].lson=merge(L,treap[R].lson);
		update(R);
		return R;
	}
}
ll insert(ll id,ll num){
	ll L=0,R=0;
	split(rt[id],num,L,R);
	new_node(num);
	rt[id]=merge(merge(L,tot),R);
	return tot;
}
void build(ll id,ll L,ll R){
	for(int i=L;i<=R;i++)insert(id,a[i]);
//	cout<<rt[id]<<"<<\n";
	if(L!=R){
		ll mid=(L+R)>>1;
		build(id<<1,L,mid);
		build(id<<1|1,mid+1,R);
	}
	return;
}
ll rk(ll id,ll num){
	ll L=0,R=0,res=1;
	split(rt[id],num-1,L,R);
	if(L)res=treap[L].sz+1;
	rt[id]=merge(L,R);
	return res;
}
ll query_rk(ll id,ll L,ll R,ll QL,ll QR,ll num){
	if(R<QL||L>QR)return 0;
	if(QL<=L&&R<=QR)return rk(id,num);
	ll mid=(L+R)>>1;
	return query_rk(id<<1,L,mid,QL,QR,num)+query_rk(id<<1|1,mid+1,R,QL,QR,num);
}
ll kth(ll now,ll num){
//	cout<<num<<" ?!\n";
	if(treap[treap[now].lson].sz+1==num)return now;
	if(treap[treap[now].lson].sz>=num){
//		cout<<"LLL\n";
		return kth(treap[now].lson,num);
	}
	return kth(treap[now].rson,num-(treap[treap[now].lson].sz+1));
}
ll query_kth(ll L,ll R,ll num){
	ll _L=0,_R=1e8;
	while(_L<=_R){
		ll mid=(_L+_R)>>1,res=query_rk(1,1,n,L,R,mid);
		if(res<=num)_L=mid+1;
		else _R=mid-1;
	}
	return _R;
}
ll del(ll id,ll num){
	ll L,R,M;
	split(rt[id],num,L,R);
	split(L,num-1,L,M);
	M=merge(treap[M].lson,treap[M].rson);
	rt[id]=merge(merge(L,M),R);
	return rt[id];
}
void update_del(ll id,ll L,ll R,ll k,ll num){
	del(id,a[k]);
	insert(id,num);
	if(L==R)return;
	ll mid=(L+R)>>1;
	if(k<=mid)update_del(id<<1,L,mid,k,num);
	else update_del(id<<1|1,mid+1,R,k,num);
	return;
}
ll pre(ll id,ll num){
	ll L=0,R=0,res=-2147483647;
	split(rt[id],num-1,L,R);
	if(L)res=treap[kth(L,treap[L].sz)].val;
	rt[id]=merge(L,R);
	return res;
}
ll query_pre(ll id,ll L,ll R,ll QL,ll QR,ll num){
	if(R<QL||L>QR)return -2147483647;
	if(QL<=L&&R<=QR)return pre(id,num);
	ll mid=(L+R)>>1;
	return max(query_pre(id<<1,L,mid,QL,QR,num),query_pre(id<<1|1,mid+1,R,QL,QR,num));
}
ll nxt(ll id,ll num){
	ll L=0,R=0,res=2147483647;
	split(rt[id],num,L,R);
	if(R)res=treap[kth(R,1)].val;
	rt[id]=merge(L,R);
	return res;
}
ll query_nxt(ll id,ll L,ll R,ll QL,ll QR,ll num){
	if(R<QL||L>QR)return 2147483647;
	if(QL<=L&&R<=QR)return nxt(id,num);
	ll mid=(L+R)>>1;
	return min(query_nxt(id<<1,L,mid,QL,QR,num),query_nxt(id<<1|1,mid+1,R,QL,QR,num));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			cout<<query_rk(1,1,n,x,y,z)<<'\n';
		} 
		else if(op==2){
			cin>>x>>y>>z;
			cout<<query_kth(x,y,z)<<'\n';
		}
		else if(op==3){
			cin>>x>>y;
			update_del(1,1,n,x,y);
			a[x]=y;
		}
		else if(op==4){
			cin>>x>>y>>z;
			cout<<query_pre(1,1,n,x,y,z)<<'\n';
		}
		else{
			cin>>x>>y>>z;
			cout<<query_nxt(1,1,n,x,y,z)<<'\n';
		}
	}
	return 0;
}