没啥重要的事情，就是终于过了这题非常开心，发现自己是莫队的时间戳部分写错了调了 114514 年我也只能说是十分趣味。
以及今天深刻地认识到了带修莫队应该 len=pow(n,0.66);。
就是裸的带修莫队+值域分块，就不说了，直接放代码了昂。
如果有人写这个做法的话或许这可以带来一点帮助？
加了光读，用的普通 cout，总用时 945ms，每个测试点用时不超过 150ms！说实话跑得真的很快啊！重铸根号荣光！ 我不是根号批。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
#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;
const int N=5e4+113,V=1e5+113,sq=360,Zi_Gao=2147483647;
int n,m,a[N],cnt_que,cnt_upd,ans[N],idx;
int id[V],bl[sq],br[sq],len,vmax,b[V],sum[sq],cnt[V];
il int read(){
re 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;
}
struct query{
int op,l,r,x,t,id;
}q[N];
il bool cmp(query x,query y){
if(id[x.l]^id[y.l])return x.l<y.l;
if(id[x.r]^id[y.r])return x.r<y.r;
return x.t<y.t;
}
struct update{
int place,x;
}u[N];
il void init(){
for(re int i=1;i<=cnt_upd;i++)b[++idx]=u[i].x;
for(re int i=1;i<=cnt_que;i++)
if(q[i].op!=2)b[++idx]=q[i].x;
vmax=idx;
sort(b+1,b+1+vmax);
vmax=unique(b+1,b+1+vmax)-b-1;
len=sqrt(vmax);
for(re int i=1;i<=vmax;i++)id[i]=(i-1)/len+1;
for(re int i=1;i<=id[vmax];i++)
bl[i]=br[i-1]+1,br[i]=i*len;
br[id[vmax]]=vmax;
for(re int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+vmax,a[i])-b;
for(re int i=1;i<=cnt_upd;i++)
u[i].x=lower_bound(b+1,b+1+vmax,u[i].x)-b;
for(re int i=1;i<=cnt_que;i++)
if(q[i].op!=2)q[i].x=lower_bound(b+1,b+1+vmax,q[i].x)-b;
}
#define Add(x) cnt[x]++,sum[id[x]]++
#define Del(x) cnt[x]--,sum[id[x]]--
il int solve_1(int x){
int res=0;
for(re int i=1;i<id[x];i++)res+=sum[i];
for(re int i=bl[id[x]];i<x;i++)res+=cnt[i];
return res+1;
}
il int solve_2(int x){
int tot=0;
for(re int i=1;i<=id[vmax];i++){
tot+=sum[i];
if(tot>=x){
tot-=sum[i];
for(re int j=bl[i];j<=br[i];j++){
tot+=cnt[j];
if(tot>=x)return b[j];
}
}
}
return Zi_Gao;
}
il int solve_4(int x){
for(re int i=x-1;i>=bl[id[x]];i--)
if(cnt[i])return b[i];
for(re int i=id[x]-1;i;i--)
if(sum[i])
for(re int j=br[i];j>=bl[i];j--)
if(cnt[j])return b[j];
return -Zi_Gao;
}
il int solve_5(int x){
for(re int i=x+1;i<=br[id[x]];i++)
if(cnt[i])return b[i];
for(re int i=id[x]+1;i<=id[vmax];i++)
if(sum[i])
for(re int j=bl[i];j<=br[i];j++)
if(cnt[j])return b[j];
return Zi_Gao;
}
int main(){
n=read(),m=read();
len=pow(n,0.66);
for(re int i=1;i<=n;i++)
a[i]=read(),id[i]=(i-1)/len+1,b[++idx]=a[i];
for(re int i=1;i<=m;i++){
int op=read();
if(op==3){
cnt_upd++;
u[cnt_upd].place=read(),u[cnt_upd].x=read();
continue;
}
cnt_que++;
q[cnt_que].op=op,q[cnt_que].l=read(),q[cnt_que].r=read(),q[cnt_que].x=read();
q[cnt_que].t=cnt_upd,q[cnt_que].id=cnt_que;
}
sort(q+1,q+1+cnt_que,cmp);
init();
re int L=1,R=0,T=0;
for(re int i=1;i<=cnt_que;i++){
re int l=q[i].l,r=q[i].r,x=q[i].x,op=q[i].op;
while(R<r)R++,Add(a[R]);
while(L>l)L--,Add(a[L]);
while(R>r)Del(a[R]),R--;
while(L<l)Del(a[L]),L++;
while(T<q[i].t){
T++;
int pla=u[T].place;
if(pla>=l&&pla<=r)Del(a[pla]),Add(u[T].x);
swap(u[T].x,a[pla]);
}
while(T>q[i].t){
int pla=u[T].place;
if(pla>=l&&pla<=r)Del(a[pla]),Add(u[T].x);
swap(u[T].x,a[pla]);
T--;
}
if(op==1)ans[q[i].id]=solve_1(x);
if(op==2)ans[q[i].id]=solve_2(x);
if(op==4)ans[q[i].id]=solve_4(x);
if(op==5)ans[q[i].id]=solve_5(x);
}
for(re int i=1;i<=cnt_que;i++)cout<<ans[i]<<'\n';
return 0;
}