本人的$O(n^{1.5})$分块，死活过不去。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define B 320
#define BK 320
#define S 100000
namespace IO {
	inline char nc(){
		static char buf[100000],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	}
	template<typename T> inline T read(){
		char ch=nc(); T sum=0; bool f=false;
		for(;ch<'0'||ch>'9';ch=nc()) if(ch=='-') f=1;
		while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
		return f ? -sum : sum;
	}
}
#define read IO::read<int>
int bl[320],br[320],ku[100010],sz[100010],K;
void fenk(int n)
{
    while(1)
    {
        K+=1;bl[K]=br[K-1]+1;
        br[K]=bl[K]+BK-1;
        if(br[K]>=n)
            {br[K]=n;break;}
    }
    for(int i=1;i<=K;i++)
        for(int j=bl[i];j<=br[i];j++)ku[j]=i;
}
struct lin
{
    int s1[100010],s2[320],pp[321],cz,kl,kr;short qq[100010];
    void lisan()
    {
        for(int i=kl,j=0;i<=kr;i++)
        {
            int z=sz[i];
            if(qq[z]==0)qq[z]=++j;
            pp[sz[i]=qq[z]]=z;
        }
    }
    void baoli(int l,int r,int x,int y)
    {
        for(int i=kl;i<=kr;i++)
        {
            sz[i]=pp[sz[i]];
            qq[sz[i]]=0;
        }
        for(int i=l;i<=r;i++)
            if(sz[i]==x)sz[i]=y,cz+=1;
        lisan();
    }
    void solve(int x,int y,int lx,int ly)
    {
        int sx=s1[x]-lx,sy=s1[y]-ly;
        if(sx==0)return;
        if(sy==0)
        {
            pp[qq[x]]=y;cz=sx;
            qq[y]=qq[x];qq[x]=0;
            return;
        }
        baoli(kl,kr,x,y);
    }
}zz[320];
void modify(int l,int r,int x,int y)
{
    if(x==y)return;
    int a=ku[l],b=ku[r],kx=x/B,ky=y/B;
    for(int i=1;i<=K;i++)zz[i].cz=0;
    if(a<b)
    {
        zz[a].baoli(l,br[a],x,y);
        for(int i=a+1;i<b;i++)
            zz[i].solve(x,y,zz[i-1].s1[x],zz[i-1].s1[y]);
        zz[b].baoli(bl[b],r,x,y);
    }
    else zz[a].baoli(l,r,x,y);
    for(int i=a;i<=K;i++)
    {
        int t=(zz[i].cz+=zz[i-1].cz);
        zz[i].s1[x]-=t;zz[i].s1[y]+=t;
    }
    if(kx!=ky)
    {
        for(int i=a;i<=K;i++)
        {
            zz[i].s2[kx]-=zz[i].cz;
            zz[i].s2[ky]+=zz[i].cz;
        }
    }
}
int ff[100010],gg[320],st[100010],tp;
void lingsan(int l,int r,int k)
{
    for(int j=l;j<=r;j++)
    {
        int z=zz[k].pp[sz[j]];
        st[tp++]=z;ff[z]+=1;gg[z/B]+=1;
    }
}
int main()
{
    int n,m;
    n=read();m=read();
    fenk(n);
    for(int i=1;i<=n;i++)
    {
        sz[i]=read();int k=ku[i],a=sz[i];
        zz[k].s1[a]+=1;zz[k].s2[a/B]+=1;
    }
    for(int x=1;x<=K;x++)
    {
        for(int i=1;i<=100000;i++)
            zz[x].s1[i]+=zz[x-1].s1[i];
        for(int i=0;i<=312;i++)
            zz[x].s2[i]+=zz[x-1].s2[i];
        zz[x].kl=bl[x];zz[x].kr=br[x];
        zz[x].lisan();
    }
    for(int i=0;i<m;i++)
    {
        int lx,l,r,x;
        lx=read();l=read();r=read();x=read();
        if(lx==1)
        {
            int y=read();
            modify(l,r,x,y);
        }
        else
        {
            int a=ku[l],b=ku[r],w=0;tp=0;
            if(a==b)
                lingsan(l,r,a),a-=1;
            else
                lingsan(l,br[a],a),lingsan(bl[b],r,b);
            while(1)
            {
                int s=zz[b-1].s2[w]-zz[a].s2[w]+gg[w];
                if(x<=s)break;x-=s;w+=1;
            }
            w*=B;
            while(x>0)
            {
                x-=zz[b-1].s1[w]-zz[a].s1[w]+ff[w];
                w+=1;
            }
            for(int j=0;j<tp;j++)
                ff[st[j]]=gg[st[j]/B]=0;
            printf("%d\n",w-1);
        }
    }
    return 0;
}