首先显然可以直接树套树做，在权值线段树上二分即可。
但是这里数据 1e5 并且可以离线，我们可以想到直接莫队/值域分块来做。
那么直接带修莫队暴力维护即可。
代码：
#include<bits/stdc++.h>
const int M=1e5+5;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
int n,m,p,len,cnt1,cnt2,a[M],lsh[M<<1],ans[M];
int CB[M],num[M<<1];
int L=1,R=0,T=0;
struct Query{
int L,R,t,p1,p2,id;
inline bool operator<(const Query&it)const{return p1==it.p1?p2==it.p2?t<it.t:R<it.R:L<it.L;}
}q[M];
struct Mdf{int id,val;}mdf[M];
inline void swap(int&x,int&y){x^=y^=x^=y;}
inline void Add(const int&val){--CB[num[val]];++CB[++num[val]];}
inline void Del(const int&val){--CB[num[val]];++CB[--num[val]];}
inline void Modify(const int&id){if(L<=mdf[id].id&&mdf[id].id<=R) Del(a[mdf[id].id]),Add(mdf[id].val);swap(a[mdf[id].id],mdf[id].val);}
signed main(){
read(n),read(m);p=2134;
for(int i=1;i<=n;++i) read(a[i]),lsh[++len]=a[i];
for(int i=1;i<=m;++i){
int f;read(f);
if(f==1){
++cnt1;
read(q[cnt1].L),read(q[cnt1].R);
q[cnt1].t=cnt2;q[cnt1].id=cnt1;q[cnt1].p1=q[cnt1].L/p,q[cnt1].p2=q[cnt1].R/p;
}
else{
++cnt2;
read(mdf[cnt2].id),read(mdf[cnt2].val);
lsh[++len]=mdf[cnt2].val;
}
}
std::sort(lsh+1,lsh+len+1);len=std::unique(lsh+1,lsh+len+1)-lsh-1;
for(int i=1;i<=n;++i)a[i]=std::lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
for(int i=1;i<=cnt2;++i)mdf[i].val=std::lower_bound(lsh+1,lsh+len+1,mdf[i].val)-lsh;
std::sort(q+1,q+cnt1+1);
for(int i=1;i<=cnt1;++i){
const int&QL=q[i].L,&QR=q[i].R,&QT=q[i].t;
while(R<QR)Add(a[++R]);
while(L>QL)Add(a[--L]);
while(L<QL)Del(a[L++]);
while(R>QR)Del(a[R--]);
while(T<QT)Modify(++T);
while(T>QT)Modify(T--);
for(int&cur=ans[q[i].id]=1;CB[cur];++cur);
}
for(int i=1;i<=cnt1;++i) write(ans[i]),putchar('
');
return 0;
}