题目链接：传送门
题解：线段树套splay
//by sdfzchy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls t[x].ch[0]
#define rs t[x].ch[1]
#define pa t[x].fa
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=3000010,mod=1e9+7;
int n,m,a[N];
struct node
{
int ch[2],fa,siz,cnt,val;
}t[N];
struct seg
{
int l,r,rt;
}c[N];
inline int in()
{
char tmp=getchar();
int res=0,f=1;
while((tmp<'0'||tmp>'9')&&tmp!='-')tmp=getchar();
if(tmp=='-') f=-1,tmp=getchar();
while(tmp>='0'&&tmp<='9') res=(res<<1)+(res<<3)+(tmp^48),tmp=getchar();
return res*f;
}
inline void upd(int x) {t[x].siz=t[ls].siz+t[rs].siz+t[x].cnt;}
inline int gi(int x) {return t[pa].ch[1]==x;}
inline void rot(int x)
{
int f=pa,g=t[f].fa,o=gi(x);
if(g) t[g].ch[gi(f)]=x;t[x].fa=g;
t[f].ch[o]=t[x].ch[!o];t[t[x].ch[!o]].fa=f;
t[x].ch[!o]=f;t[f].fa=x;
upd(f),upd(x);
}
int cur,cnt,ans,tmp;
inline void splay(int x,int tar,int &root)
{
for(;pa!=tar;rot(x))
if(t[pa].fa!=tar)
rot((gi(x)==gi(pa))?pa:x);
if(!tar) root=x;
}
inline void newnode(int &x,int val)
{
x=++cnt;
ls=rs=0;
t[x].siz=t[x].cnt=1;
t[x].val=val;
}
void ins(int &x,int fa,int w)
{
int k=x;
if(!x) {newnode(x,w);pa=fa;return;}
t[x].siz++;
if(t[x].val==w) {t[x].cnt++;return;}
else if(w>t[x].val) ins(rs,x,w);
else ins(ls,x,w);
}
void rank(int x,int k)
{
while(x)
{
if(k<=t[x].val) x=ls;
else tmp+=t[ls].siz+t[x].cnt,x=rs;
}
}
int kth(int x,int k)
{
if(k<t[x].val) return kth(ls,k);
else if(k==t[x].val) return x;
else return kth(rs,k);
}
void del(int &root,int val)
{
int x=kth(root,val);
splay(x,0,root);
if(t[x].cnt>1) {t[x].cnt--;t[x].siz--;return;}
if(!ls&&!rs) root=0;
else if(rs==0) t[ls].fa=0,root=ls;
else if(ls==0) t[rs].fa=0,root=rs;
else
{
int pos=ls;
while(t[pos].ch[1]) pos=t[pos].ch[1];
splay(pos,x,root);
t[pos].ch[1]=rs;t[rs].fa=pos;
t[pos].fa=0;root=pos;
upd(root);
}
}
void change(int pos,int rt,int val,int las)
{
del(c[rt].rt,las);
ins(c[rt].rt,0,val);
int l=c[rt].l,r=c[rt].r,mid=(l+r)>>1;
if(l==r) return;
if(pos<=mid) change(pos,rt<<1,val,las);
else change(pos,rt<<1|1,val,las);
}
void build(int l,int r,int rt)
{
c[rt].l=l;c[rt].r=r;
for(int i=l;i<=r;i++) ins(c[rt].rt,0,a[i]);
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void pre(int x,int k)
{
if(!x) return;
if(t[x].val<k) ans=max(ans,t[x].val),pre(rs,k);
else pre(ls,k);
}
void suc(int x,int k)
{
if(!x) return;
if(t[x].val>k) ans=min(ans,t[x].val),suc(ls,k);
else suc(rs,k);
}
void gik(int x,int y,int rt,int k)
{
int l=c[rt].l,r=c[rt].r,mid=(l+r)>>1;
if(x==l&&r==y) rank(c[rt].rt,k);
else if(x>mid) gik(x,y,rt<<1|1,k);
else if(y<=mid) gik(x,y,rt<<1,k);
else gik(x,mid,rt<<1,k),gik(mid+1,y,rt<<1|1,k);
}
void gipre(int x,int y,int rt,int k)
{
int l=c[rt].l,r=c[rt].r,mid=(l+r)>>1;
if(x==l&&r==y) pre(c[rt].rt,k);
else if(x>mid) gipre(x,y,rt<<1|1,k);
else if(y<=mid) gipre(x,y,rt<<1,k);
else gipre(x,mid,rt<<1,k),gipre(mid+1,y,rt<<1|1,k);
}
void gisuc(int x,int y,int rt,int k)
{
int l=c[rt].l,r=c[rt].r,mid=(l+r)>>1;
if(x==l&&r==y) suc(c[rt].rt,k);
else if(x>mid) gisuc(x,y,rt<<1|1,k);
else if(y<=mid) gisuc(x,y,rt<<1,k);
else gisuc(x,mid,rt<<1,k),gisuc(mid+1,y,rt<<1|1,k);
}
int main()
{
n=in(),m=in();
for(int i=1;i<=n;i++) a[i]=in();
build(1,n,1);
for(int i=1,op,l,r,z;i<=m;i++)
{
op=in(),l=in(),r=in();
switch(op)
{
case 1:z=in();tmp=1;gik(l,r,1,z);printf("%d\n",tmp);break;
case 2:
{
z=in();
int L=0,R=2147483647;
while(L<=R)
{
int mid=(L+R)>>1;
tmp=1;
gik(l,r,1,mid);
if(tmp<=z) L=mid+1,ans=mid;
else R=mid-1;
}
printf("%d\n",ans);
break;
}
case 3:change(l,1,r,a[l]);a[l]=r;break;
case 4:z=in();ans=-2147483647;gipre(l,r,1,z);printf("%d\n",ans);break;
case 5:z=in();ans=2147483647;gisuc(l,r,1,z);printf("%d\n",ans);break;
}
}
/* for(int i=1;i<=n;i++) { ans=2147483647; gisuc(i,i,1,0); printf("%d ",ans); } cout<<endl;*/
return 0;
}