套了个值域分块（），感觉没有写锅，但是事实上写锅了。
求调

#include <bits/stdc++.h>
using namespace std;

#define ri register int
#define ll long long

//#define Neutral Shimokitazawa //rush!

#define Tp template<class T>
#ifdef Neutral
    const int End=1e6;
    char buf[End],*p1=buf,*p2=buf;
    #define g() (p1==p2&&(p2=(p1=buf)+fread(buf,1,End,stdin),p1==p2)?EOF:*p1++)
#else
    #define g() getchar()
#endif
#define pc(x) putchar(x)
#define isd(x) (x>=48&&x<=57)
namespace SlowIO{
    Tp inline void rd(T &x) {
        x=0; char i=g(); bool f=1;
        while(!isd(i)) f&=(i!='-'),i=g();
        while(isd(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
        x*=((f<<1)-1);
    }
    const int OUT=1e6;
    static char outp[OUT]; int out;
    Tp inline void op(T x){
        out=0; x<0&&(x=-x,pc('-'));
        if(!x){ pc(48); return; }
        while(x) outp[++out]=x%10+48,x/=10;
        while(out) pc(outp[out--]);
    }
    Tp inline void writeln(T x){ op(x);pc('\n'); }
    Tp inline void writesp(T x){ op(x); pc(' '); }
    Tp inline void write(T x,char c=0){ op(x); c&&pc(c); }
}; using namespace SlowIO;

#define N 100003
#define lbw lower_bound
//lenb = n^{\frac{k-1}{k}}
int a[N],b[N<<1],lenq,belq[N];
int lenv,belv[N<<1],L[651],R[651];
int siz[651],cnt[N<<1],tag[N];
struct qry{
    int l,r,t,id;
    inline bool operator <(const qry &a) const{
        if(belq[l]^belq[a.l]) return belq[l]<belq[a.l];
        if(belq[t]^belq[a.t]) return belq[t]<belq[a.t];
        return ((belq[l]+belq[t])&1)?r<a.r:r>a.r;
    }
}qr[N];
struct chg{
    int pos,val;
}ch[N]; int ans[N];
inline void get_block(int n){
    lenq=pow(n,2.0/3.0),lenv=sqrt(n); L[1]=1;
    for(ri i=1;i<=n;++i){
        belv[i]=(i-1)/lenv+1,belq[i]=(i-1)/lenq+1;
        if(belv[i]^belv[i-1]) L[belv[i]]=i,R[belv[i]-1]=i-1;
    } R[belv[n]]=n;
}
inline void Add(int x){
    if(tag[cnt[a[x]]]==1) --siz[belv[cnt[a[x]]]];
    --tag[cnt[a[x]]],++cnt[a[x]],++tag[cnt[a[x]]];
    if(tag[cnt[a[x]]]==1) ++siz[belv[cnt[a[x]]]];
}
inline void Del(int x){
    if(tag[cnt[a[x]]]==1) --siz[belv[cnt[a[x]]]];
    --tag[cnt[a[x]]],--cnt[a[x]],++tag[cnt[a[x]]];
    if(tag[cnt[a[x]]]==1) ++siz[belv[cnt[a[x]]]];
}
inline void Chg(int id,int l,int r){
    ri x=ch[id].pos,&v=ch[id].val;
    if(x>=l&&x<=r){ //如果不在区间里就没有贡献！！！1
        Del(x);
        if(tag[cnt[v]]==1) --siz[belv[cnt[v]]];
        --tag[cnt[v]],++cnt[v],++tag[cnt[v]];
        if(tag[cnt[v]]==1) ++siz[belv[cnt[v]]];
    } swap(v,a[x]);
} int n,m;
inline int Mex(){
    ri idx=1; while(siz[idx]==lenv) ++idx;
    if(!L[idx]) return R[idx-1]+1;
    for(ri i=L[idx];i<=R[idx];++i)
        if(!tag[i]) return i;
}

int main()
{
    rd(n),rd(m);
    for(ri i=1;i<=n;++i) rd(a[i]),b[i]=a[i];
    int tot=n,cnt_q=0,cnt_c=0,len;
    for(ri i=1;i<=m;++i){
        int cho,l,r; rd(cho),rd(l),rd(r);
        if(cho&1) ++cnt_q,qr[cnt_q]={l,r,cnt_c,cnt_q};
        else ++cnt_c,ch[cnt_c]={l,b[++tot]=r};
    } sort(b+1,b+tot+1),len=unique(b+1,b+tot+1)-b-1;
    for(ri i=1;i<=n;++i) a[i]=lbw(b+1,b+len+1,a[i])-b;
    for(ri i=1;i<=cnt_c;++i) ch[i].val=lbw(b+1,b+len+1,ch[i].val)-b;
    get_block(n),sort(qr+1,qr+cnt_q+1);
    ri cl=1,cr=0,ct=0,lef,rig,mdf;
    for(ri i=1;i<=cnt_q;++i){
        lef=qr[i].l,rig=qr[i].r,mdf=qr[i].t;
        while(cl>lef) Add(--cl);
        while(cr<rig) Add(++cr);
        while(ct<mdf) Chg(++ct,lef,rig);
        while(cl<lef) Del(cl++);
        while(cr>rig) Del(cr--);
        while(ct>mdf) Chg(ct--,lef,rig);
        ans[qr[i].id]=Mex();
    } for(ri i=1;i<=cnt_q;++i) writeln(ans[i]);
    return 0;
}