记录

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

int cre,n,m,a[100001],b[1001][1001],tb[1001],tc[100001],Block[100001],c[501][100001],B=400,V=1e5,which[501][100001],which_[501][100001],vec[1001],h;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=V;++i)
        Block[i]=((i-1)/B)+1;
    for(int i=1;i<=n;++i)
        cin>>a[i],
        ++b[Block[i]][Block[a[i]]],
        ++c[Block[i]][a[i]];
    for(int i=1;i<=Block[n];++i)
    {
        for(int j=1;j<=Block[V];++j)
            b[i][j]+=b[i-1][j];
        for(int j=1;j<=V;++j)
            c[i][j]+=c[i-1][j],which[i][j]=which_[i][j]=j;
    }
    while(m--)
    {
        int op,l,r,x,y;
        cin>>op>>l>>r;
        int la=Block[l],ra=Block[r];
        if(op==1)
        {
            cin>>x>>y;
            if(x==y)continue;
            h=0;
            for(int i=ra*B-B+1;i<=min(ra*B,n);++i)
                vec[++h]=a[i],a[i]=which[ra][a[i]],which_[ra][a[i]]=a[i];
            for(int i=1;i<=h;++i)which[ra][vec[i]]=vec[i];
            if(la==ra)
            {
                int cnt=0;
                for(int i=l;i<=r;++i)
                    if(a[i]==x)++cnt,a[i]=y;
                for(int i=la;i<=Block[n];++i)
                    b[i][Block[x]]-=cnt,b[i][Block[y]]+=cnt,c[i][x]-=cnt,c[i][y]+=cnt;
                continue;
            }
            h=0;
            for(int i=la*B-B+1;i<=la*B;++i)
                vec[++h]=a[i],a[i]=which[la][a[i]],which_[la][a[i]]=a[i];
            for(int i=1;i<=h;++i)which[la][vec[i]]=vec[i];
            int cnt=0;
            for(int i=l;i<=la*B;++i)
                if(a[i]==x)++cnt,a[i]=y;
            int las=c[la][x],las_=c[la][y];
            b[la][Block[x]]-=cnt,b[la][Block[y]]+=cnt,c[la][x]-=cnt,c[la][y]+=cnt;
            for(int i=la+1;i<ra;++i)
            {
                if(c[i][x]==las)
                {
                    cnt+=c[i][x]-las;
                    las=c[i][x];
                    las_=c[i][y];
                    b[i][Block[x]]-=cnt;
                    c[i][x]-=cnt;
                    b[i][Block[y]]+=cnt;
                    c[i][y]+=cnt;
                    continue;
                }
                if(c[i][y]==las_)
                    which[i][which_[i][x]]=y,which_[i][y]=which_[i][x],which_[i][x]=x;
                else
                {
                    h=0;
                    for(int j=i*B-B+1;j<=i*B;++j)
                        vec[++h]=a[j],a[j]=which[i][a[j]],which_[i][a[j]]=a[j];
                    for(int j=1;j<=h;++j)which[i][vec[j]]=vec[j];
                    for(int j=i*B-B+1;j<=i*B;++j)
                        if(a[j]==x)a[j]=y;
                }
                cnt+=c[i][x]-las;
                las=c[i][x];
                las_=c[i][y];
                b[i][Block[x]]-=cnt;
                c[i][x]-=cnt;
                b[i][Block[y]]+=cnt;
                c[i][y]+=cnt;
            }
            for(int i=ra*B-B+1;i<=r;++i)
                if(a[i]==x)++cnt,a[i]=y;
            for(int i=ra;i<=Block[n];++i)
                b[i][Block[x]]-=cnt,
                c[i][x]-=cnt,
                b[i][Block[y]]+=cnt,
                c[i][y]+=cnt;
        }
        else
        {
            cin>>x;
            h=0;
            for(int i=ra*B-B+1;i<=min(ra*B,n);++i)
                vec[++h]=a[i],a[i]=which[ra][a[i]],which_[ra][a[i]]=a[i];
            for(int i=1;i<=h;++i)which[ra][vec[i]]=vec[i];
            if(la==ra)
            {
                for(int i=l;i<=r;++i)
                    ++tb[Block[a[i]]],++tc[a[i]];
                int cnt=0;
                for(int i=1;i<=Block[V];++i)
                {
                    if(cnt+tb[i]<x)cnt+=tb[i];
                    else
                    {
                        for(int j=i*B-B+1;j<=i*B;++j)
                        {
                            if(cnt+tc[j]<x)cnt+=tc[j];
                            else 
                            {
                                cout<<j<<"\n";
                                break;
                            }
                        }
                        break;
                    }
                }
                for(int i=l;i<=r;++i)
                    tb[Block[a[i]]]=tc[a[i]]=0;
                continue;
            }
            h=0;
            for(int i=la*B-B+1;i<=la*B;++i)
                vec[++h]=a[i],a[i]=which[la][a[i]],which_[la][a[i]]=a[i];
            for(int i=1;i<=h;++i)which[la][vec[i]]=vec[i];
            for(int i=l;i<=la*B;++i)
                ++tb[Block[a[i]]],++tc[a[i]];
            for(int i=ra*B-B+1;i<=r;++i)
                ++tb[Block[a[i]]],++tc[a[i]];
            int cnt=0;
            for(int i=1;i<=Block[V];++i)
            {
                if(cnt+b[ra-1][i]-b[la][i]+tb[i]<x)cnt+=b[ra-1][i]-b[la][i]+tb[i];
                else
                {
                    for(int j=i*B-B+1;j<=i*B;++j)
                    {
                        if(cnt+c[ra-1][j]-c[la][j]+tc[j]<x)cnt+=c[ra-1][j]-c[la][j]+tc[j];
                        else 
                        {
                            cout<<j<<"\n";
                            break;
                        }
                    }
                    break;
                }
            }
            for(int i=l;i<=la*B;++i)
                tb[Block[a[i]]]=tc[a[i]]=0;
            for(int i=ra*B-B+1;i<=r;++i)
                tb[Block[a[i]]]=tc[a[i]]=0;
        }
    }
}