TLE一个点1.09s，瞎调块长没过。

#include<bits/stdc++.h>
using namespace std;
namespace fastio
{
    const int bufl=1<<16;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
        IN& operator>>(__int128 &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        IN& operator>>(long double &a){getDouble(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putInt(b);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        OUT& operator<<(__int128 a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        OUT& operator<<(long double a){putDouble(a);return *this;}
        ~OUT(){flush();}
    };
}
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;
const int N=1e5+5;
const int K=325;
int n,m;
int a[N];

int k,l[K],r[K];
int zk[K][N],kk[K][K];
int fa[N],si[N];
int z[K][N];
int id[N];

int anz[N],ank[K];
int kid[N],kc;
int lk[N],rk[N];

inline int find(const int& y){return fa[y]==y?y:fa[y]=find(fa[y]);}
inline void me(const int& x,const int& y){
    si[find(x)]+=si[find(y)];
    fa[find(y)]=find(x);
}
int op,ll,rr,x,y,lid,rid,xid,yid;
int main(){
    fin>>n>>m;
    k=(n-1)/316+1;kc=316;
    for(register int i=1;i<=k;++i){
        l[i]=r[i-1]+1;
        r[i]=i*316;
    }r[k]=n;
    for(register int i=1;i<=kc;++i){
        lk[i]=rk[i-1]+1;
        rk[i]=i*kc;
    }rk[kc]=100000;
    for(register int i=1;i<=k;++i){
        for(register int j=l[i];j<=r[i];++j){
            id[j]=i;
        }
    }
    for(register int i=1;i<=kc;++i){
        for(register int j=lk[i];j<=rk[i];++j){
            kid[j]=i;
        }
    }
    for(register int i=1;i<=n;++i){
        fin>>a[i];
    }
    for(register int i=1;i<=k;++i){
        for(register int j=l[i];j<=r[i];++j){
            fa[j]=j;
            si[j]=1;
            zk[i][a[j]]++;
            kk[i][kid[a[j]]]++;
            if(z[i][a[j]]==0){
                z[i][a[j]]=j;
            }
            else{
                me(z[i][a[j]],j);
            }
        }
        for(register int j=1;j<=kc;++j){
            kk[i][j]+=kk[i-1][j];
        }
        for(register int j=1;j<=n;++j){
            zk[i][j]+=zk[i-1][j];
        }
    }
    while(m--){
        fin>>op>>ll>>rr>>x;lid=id[ll],rid=id[rr];
        if(op==2){
            if(lid==rid){
                for(register int i=ll;i<=rr;++i){
                    a[i]=a[find(i)];
                    anz[i]=a[i];
                }
                nth_element(anz+ll,anz+ll+x-1,anz+rr+1);
                fout<<anz[ll+x-1]<<'\n';
                for(register int i=ll;i<=rr;++i){
                    anz[i]=0;
                }
                continue;
            }
            for(register int i=ll;i<l[lid+1];++i){
                a[i]=a[find(i)];
                anz[a[i]]++;
                ank[kid[a[i]]]++;
            }
            for(register int i=l[rid];i<=rr;++i){
                a[i]=a[find(i)];
                anz[a[i]]++;
                ank[kid[a[i]]]++;
            }
            for(register int i=1;i<=kc;++i){
                if(x>ank[i]+kk[id[rr]-1][i]-kk[id[ll]][i]){
                    x-=ank[i]+kk[id[rr]-1][i]-kk[id[ll]][i];
                }
                else{
                    for(register int j=lk[i];j<=rk[i];++j){
                        if(x>anz[j]+zk[rid-1][j]-zk[lid][j]){
                            x-=anz[j]+zk[rid-1][j]-zk[lid][j];
                        }
                        else{
                            fout<<j<<'\n';
                            break;
                        }
                    }
                    break;
                }
            }
            for(register int i=ll;i<l[lid+1];++i){
                anz[a[i]]--;
                ank[kid[a[i]]]--;
            }
            for(register int i=l[rid];i<=rr;++i){
                anz[a[i]]--;
                ank[kid[a[i]]]--;
            }
        }
        else{
            fin>>y;xid=kid[x],yid=kid[y];
            if(x==y)continue;
            if(zk[rid][x]-zk[lid-1][x]==0)continue;
            for(register int i=k;i>=lid;--i){
                zk[i][y]-=zk[i-1][y];
                kk[i][yid]-=kk[i-1][yid];
                zk[i][x]-=zk[i-1][x];
                if(yid!=xid)kk[i][xid]-=kk[i-1][xid];
            }
            if(lid==rid){
                for(register int i=l[lid];i<=r[lid];++i){
                    a[i]=a[find(i)];
                }
                for(register int i=l[lid];i<=r[lid];++i){
                    z[lid][a[i]]=0;
                    fa[i]=i;
                    si[i]=1;
                }
                for(register int i=ll;i<=rr;++i){
                    if(a[i]==x){
                        zk[lid][x]--;
                        zk[lid][y]++;
                        kk[lid][xid]--;
                        kk[lid][yid]++;
                        a[i]=y;
                    }
                }
                for(register int i=l[lid];i<=r[lid];++i){
                    if(z[lid][a[i]]==0){
                        z[lid][a[i]]=i;
                    }
                    else{
                        me(z[lid][a[i]],i);
                    }
                }
                for(register int i=lid;i<=k;++i){
                    zk[i][y]+=zk[i-1][y];
                    kk[i][yid]+=kk[i-1][yid];
                    zk[i][x]+=zk[i-1][x];
                    if(yid!=xid)kk[i][xid]+=kk[i-1][xid];
                }
                continue;
            }
            for(register int i=l[lid];i<=r[lid];++i){
                a[i]=a[find(i)];
            }
            for(register int i=l[lid];i<=r[lid];++i){
                z[lid][a[i]]=0;
                fa[i]=i;
                si[i]=1;
            }
            for(register int i=ll;i<=r[lid];++i){
                if(a[i]==x){
                    zk[lid][x]--;
                    zk[lid][y]++;
                    kk[lid][xid]--;
                    kk[lid][yid]++;
                    a[i]=y;
                }
            }
            for(register int i=l[lid];i<=r[lid];++i){
                if(z[lid][a[i]]==0){
                    z[lid][a[i]]=i;
                }
                else{
                    me(z[lid][a[i]],i);
                }
            }
            for(register int i=l[rid];i<=r[rid];++i){
                a[i]=a[find(i)];
            }
            for(register int i=l[rid];i<=r[rid];++i){
                z[rid][a[i]]=0;
                fa[i]=i;
                si[i]=1;
            }
            for(register int i=l[rid];i<=rr;++i){
                if(a[i]==x){
                    zk[rid][x]--;
                    zk[rid][y]++;
                    kk[rid][xid]--;
                    kk[rid][yid]++;
                    a[i]=y;
                }
            }
            for(register int i=l[rid];i<=r[rid];++i){
                if(z[rid][a[i]]==0){
                    z[rid][a[i]]=i;
                }
                else{
                    me(z[rid][a[i]],i);
                }
            }
            for(register int i=lid+1;i<rid;++i){
                if(z[i][x]==0)continue;
                if(z[i][y]==0){
                    zk[i][x]-=si[z[i][x]];
                    zk[i][y]+=si[z[i][x]];
                    kk[i][xid]-=si[z[i][x]];
                    kk[i][yid]+=si[z[i][x]];
                    z[i][y]=z[i][x];
                    a[z[i][x]]=y;
                    z[i][x]=0;
                }
                else{
                    zk[i][x]-=si[z[i][x]];
                    zk[i][y]+=si[z[i][x]];
                    kk[i][xid]-=si[z[i][x]];
                    kk[i][yid]+=si[z[i][x]];
                    me(z[i][y],z[i][x]);
                    z[i][x]=0;
                }
            }
            for(register int i=lid;i<=k;++i){
                zk[i][y]+=zk[i-1][y];
                kk[i][yid]+=kk[i-1][yid];
                zk[i][x]+=zk[i-1][x];
                if(yid!=xid)kk[i][xid]+=kk[i-1][xid];
            }
        }
    }
    return 0;
}