pb_ds 0pts求调

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef pair<int,int>P;
const int maxn=5e4+10;
tree<P,null_type,less<P>,rb_tree_tag,tree_order_statistics_node_update>t[maxn<<2];
int n,m,cnt;
int query(int rt,int l,int r,int L,int R,int x){
	if(L<=l&&r<=R){
		return t[rt].order_of_key(make_pair(x,0))-1;
	}
	int mid=(l+r)>>1; int res=0;
	if(L<=mid){
		res+=query(rt<<1,l,mid,L,R,x);
	}
	if(mid<R){
		res+=query(rt<<1|1,mid+1,r,L,R,x);
	}
	return res;
}

int query1(int l,int r,int x){
	int L=0,R=1e8,mid;
	while(L<=R){
		mid=(L+R)>>1;
		if(query(1,1,n,l,r,mid)>=x)R=mid-1;
		else L=mid+1;
	}
	return L;
}

int update(int rt,int l,int r,int L,int x){
	if(l==L&&L==r){
		int p=t[rt].lower_bound(make_pair(0,0))->first;
		t[rt].erase(t[rt].lower_bound(make_pair(p,0)));
		t[rt].insert(make_pair(x,cnt++));
		return p;
	}
	int mid=(l+r)>>1; int p;
	if(L<=mid)p=update(rt<<1,l,mid,L,x);
	else p=update(rt<<1|1,mid+1,r,L,x);
	t[rt].erase(t[rt].lower_bound(make_pair(p,0)));
	t[rt].insert(make_pair(x,cnt++));
	return p;
}

int query2(int rt,int l,int r,int L,int R,int x){
	if(L<=l&&r<=R){
		return (--t[rt].lower_bound(make_pair(x,0)))->first;
	}
	int mid=(l+r)>>1; int res=-1e9;
	if(L<=mid)res=max(res,query2(rt<<1,l,mid,L,R,x));
	if(mid<R)res=max(res,query2(rt<<1|1,mid+1,r,L,R,x));
	return res;
}

int query3(int rt,int l,int r,int L,int R,int x){
	if(L<=l&&r<=R){
		return t[rt].lower_bound(make_pair(x+1,0))->first;
	}
	int mid=(l+r)>>1; int res=1e9;
	if(L<=mid)res=min(res,query3(rt<<1,l,mid,L,R,x));
	if(mid<R)res=min(res,query3(rt<<1|1,mid+1,r,L,R,x));
	return res;
}

int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		update(1,1,n,i,x);
	}
	for(int i=1;i<(n<<2);i++){
		t[i].insert(make_pair(-1e9,cnt++));
		t[i].insert(make_pair(1e9,cnt++));
	}
	while(m--){
		int op,l,r,k; cin>>op;
		if(op==1){
			cin>>l>>r>>k;
			cout<<query(1,1,n,l,r,k)<<'\n';
		}
		if(op==2){
			cin>>l>>r>>k;
			cout<<query1(l,r,k)<<'\n';
		}
		if(op==3){
			cin>>l>>k;
			update(1,1,n,l,k);
		}
		if(op==4){
			cin>>l>>r>>k;
			int p=query2(1,1,n,l,r,k);
			if(p==-1e9)cout<<-2147483647<<'\n';
			else cout<<p<<'\n';
		}
		if(op==5){
			cin>>l>>r>>k;
			int p=query3(1,1,n,l,r,k);
			if(p==1e9)cout<<2147483647<<'\n';
			else cout<<p<<'\n';
		}
	}
	return 0;
}