splayT了一个点求调

#include<iostream>
//#define int long long
#define inf 2147483647
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
int xx,f;
char ch;
inline int read(){//快读
	xx=0,f=1;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+(ch^48);ch=getchar();}
	return xx*f;
}
inline void print(int x){//快写
    if (x<0)	putchar('-'),x=-x;
    if (x>9) print(x/10);
    putchar(x%10+'0');
}
int cnt,n,m,a[50001];
struct node{
	int fa,val,siz,ch[2],tot;
}t[2000001];
struct tree{
	int l,r,root;
}tr[200001];
void push(int x){t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].tot;}
void rotate(int x){
	int fa=t[x].fa,ffa=t[fa].fa;
	int k=(t[fa].ch[1]==x);
	t[ffa].ch[t[ffa].ch[1]==fa]=x;
	t[x].fa=ffa;
	t[fa].ch[k]=t[x].ch[k^1];
	t[t[x].ch[k^1]].fa=fa;
	t[x].ch[k^1]=fa;
	t[fa].fa=x;
	push(fa);push(x);
}
void splay(int x,int gol,int &root){
	while(t[x].fa!=gol){
		int fa=t[x].fa,ffa=t[fa].fa;
		if(ffa!=gol)((t[fa].ch[0]==x)^(t[ffa].ch[0]==fa))?rotate(fa):rotate(x);
		rotate(x);	
	}
	if(!gol)root=x;
}
void insert(int k,int x,int &root){
	int fa=0;
	while(x&&t[x].val!=k){
		fa=x;
		x=t[x].ch[k>t[x].val];
	}
	if(x)t[x].tot++;
	else {
		x=++cnt;
		if(fa)t[fa].ch[k>t[fa].val]=x;
		t[x].fa=fa;
		t[x].ch[0]=t[x].ch[1]=0;
		t[x].val=k;
		t[x].tot=t[x].siz=1;
	}
	splay(x,0,root);
}
void find(int k,int x,int &root){
	if(!x)return ;
	while(t[x].ch[k>t[x].val]&&k!=t[x].val)x=t[x].ch[k>t[x].val];
	splay(x,0,root);
}
int pre(int k,int &root){
	find(k,root,root);
	if(t[root].val<k)return root;
	int x=t[root].ch[0];
	while(t[x].ch[1])x=t[x].ch[1];
	return x;
}
int nxt(int k,int &root){
	find(k,root,root);
	if(t[root].val>k)return root;
	int x=t[root].ch[1];
	while(t[x].ch[0])x=t[x].ch[0];
	return x;
}
void del(int k,int &root){
	int pr=pre(k,root),nx=nxt(k,root);
	splay(pr,0,root);
	splay(nx,pr,root);
	int x=t[nx].ch[0];
	if(t[x].tot>1)t[x].tot--,splay(x,0,root);
	else t[nx].ch[0]=0;
	push(nx);
}
int find_rank(int k,int &root){
	find(k-1,root,root);
	int u=root;
	if(t[u].val>=k)return t[t[u].ch[0]].siz-1;
	else return t[t[u].ch[0]].siz+t[u].tot-1;
}
void build(int l,int r,int x){
	insert(inf,tr[x].root,tr[x].root),insert(-inf,tr[x].root,tr[x].root);
	tr[x].l=l;tr[x].r=r;
	if(l==r)return ;
	int mid=(l+r)>>1;
	build(l,mid,x<<1);build(mid+1,r,x<<1|1);
}
void change(int p,int x,int kk,int k){
	del(kk,tr[x].root),insert(k,tr[x].root,tr[x].root);
	if(tr[x].l==tr[x].r)return ;
	int mid=(tr[x].l+tr[x].r)>>1;
	if(p<=mid)change(p,x<<1,kk,k);
	else change(p,x<<1|1,kk,k);
}
void seg_insert(int x,int p,int k){
	insert(k,tr[x].root,tr[x].root);
	if(tr[x].l==tr[x].r)return ;
	int mid=(tr[x].l+tr[x].r)>>1;
	if(p<=mid)seg_insert(x<<1,p,k);
	else seg_insert(x<<1|1,p,k);
}
int ask_pre(int l,int r,int x,int k){
	if(l<=tr[x].l&&tr[x].r<=r)return t[pre(k,tr[x].root)].val;
	int mid=(tr[x].l+tr[x].r)>>1,ans=-inf;
	if(l<=mid)ans=max(ans,ask_pre(l,r,x<<1,k));
	if(r>mid)ans=max(ans,ask_pre(l,r,x<<1|1,k));
	return ans;
}
int ask_back(int l,int r,int x,int k){
	if(l<=tr[x].l&&tr[x].r<=r)return t[nxt(k,tr[x].root)].val;
	int mid=(tr[x].l+tr[x].r)>>1,ans=inf;
	if(l<=mid)ans=min(ans,ask_back(l,r,x<<1,k));
	if(r>mid)ans=min(ans,ask_back(l,r,x<<1|1,k));
	return ans;
}
int ask_rank(int l,int r,int x,int k){
	if(l<=tr[x].l&&tr[x].r<=r){
		find(k-1,tr[x].root,tr[x].root);
		int u=tr[x].root;
		if(t[u].val>=k)return t[t[u].ch[0]].siz-1;
		else return t[t[u].ch[0]].siz+t[u].tot-1;
	}
	int mid=(tr[x].l+tr[x].r)>>1,ans=0;
	if(l<=mid)ans+=ask_rank(l,r,x<<1,k);
	if(r>mid)ans+=ask_rank(l,r,x<<1|1,k);
	return ans;
}
int ask_kth(int l,int r,int k){
	int ll=0,rr=1e8,ans=0;
	while(ll<=rr){
		int mid=(ll+rr)>>1;
		if(k<ask_rank(l,r,1,mid)+1)rr=mid-1;
		else ll=mid+1,ans=mid;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	n=read(),m=read();
	build(1,n,1);
	for(int i=1;i<=n;i++)a[i]=read(),seg_insert(1,i,a[i]);
	int op,l,r,k;
	while(m--){
		op=read(),l=read(),r=read();
		if(op==1){
			k=read();
			print(ask_rank(l,r,1,k)+1);
			putchar('\n');
		}
		else if(op==2){
			k=read();
			print(ask_kth(l,r,k));
			putchar('\n');
		}
		else if(op==3)change(l,1,a[l],r),a[l]=r;
		else if(op==4){
			k=read();
			print(ask_pre(l,r,1,k));
			putchar('\n') ;
		}
		else{
			k=read();
			print(ask_back(l,r,1,k));
			putchar('\n');
		} 
	}
}