RT，一直在 46~64 pts 徘徊。

#include<iostream>
#include<math.h>
#define S 350
using namespace std;
int n,Max,m,at,alen,st,slen;
int t1[350]={0},t2[100005]={0};
int al[S],ar[S],sl[350],sr[350];
int b[S][350],c[S][100005],fa[S][100005],rt[S][100005];
int a[100005],apos[100005],spos[100005];
inline int read(){
    char x=getchar();
    while(x<'0'||x>'9'){   
        x=getchar();
    }
    register int ans=0;
    while(x>='0'&&x<='9'){
        ans=(ans<<3)+(ans<<1)+x-'0';
        x=getchar();
    }
    return ans;
} 
inline void write(int x){
    char s[210];
    register int flag=0;
    if(x==0)
    {
    	putchar('0');
    	putchar('\n');
    	return;
	}
    while(x>0){
        s[++flag]=x%10+'0';
        x/=10;
    }
    while(flag>0)
        putchar(s[flag--]);
    putchar('\n');
}
inline int find(int i,int x)
{
	if(fa[i][x]==x)
	{
		return x;
	}
	fa[i][x]=find(i,fa[i][x]);
	return fa[i][x];
}
inline void init()
{
    alen=420;
    at=n/alen;
    slen=sqrt(Max);
    st=Max/slen;
    if(n%alen!=0)
    {
        at++;
    }
    if(Max%slen!=0)
    {
        st++;
    }
    for(register int i=1;i<=at;++i)
    {
        al[i]=(i-1)*alen+1;
        ar[i]=i*alen;
    }
    if(ar[at]>n)
    {
        ar[at]=n;
    }
    for(register int i=1;i<=st;++i)
    {
        sl[i]=(i-1)*slen+1;
        sr[i]=i*slen;
    }
    if(sr[st]>n)
    {
        sr[st]=n;
    }
    for(register int i=1;i<=at;++i)
    {
        for(register int j=al[i];j<=ar[i];++j)
        {
            apos[j]=i;
        }
    }
    for(register int i=1;i<=st;++i)
    {
        for(register int j=sl[i];j<=sr[i];++j)
        {
            spos[j]=i;
        }
    }
    for(register int i=1;i<=at;++i)
    {
    	for(register int j=al[i];j<=ar[i];++j)
	    {
	    	fa[i][j]=j;
	    	if(rt[i][a[j]])
	    	{
	    		fa[i][j]=rt[i][a[j]];
			}
			else
			{
				rt[i][a[j]]=j;
			}
	        ++b[i][spos[a[j]]];
	        ++c[i][a[j]];
	    }
	}
    for(register int i=2;i<=at;++i)
    {
    	for(register int j=1;j<=st;++j)
	    {
	        b[i][j]+=b[i-1][j];
	    }
    	for(register int j=1;j<=Max;++j)
	    {
	        c[i][j]+=c[i-1][j];
	    }
	}
}
inline int kth(int l,int r,int k)
{
	int ans=2;
	int sum=0;
	if(apos[l]==apos[r])
	{
		for(register int i=l;i<=r;++i)
		{
			++t1[spos[a[find(apos[i],i)]]];
			++t2[a[find(apos[i],i)]];
		}
		for(register int i=1;i<=st;++i)
		{
			sum+=t1[i];
			if(sum>=k)
			{
				sum-=t1[i];
				for(register int j=sl[i];j<=sr[i];++j)
				{
					sum+=t2[j];
					if(sum>=k)
					{
						ans=j;
						break;
					}
				}
				break;
			}
		}
		for(register int i=l;i<=r;++i)
		{
			--t1[spos[a[find(apos[i],i)]]];
			--t2[a[find(apos[i],i)]];
		}
	}
	else
	{
		for(register int i=l;i<=ar[apos[l]];++i)
		{
			++t1[spos[a[find(apos[i],i)]]];
			++t2[a[find(apos[i],i)]];
		}
		for(register int i=al[apos[r]];i<=r;++i)
		{
			++t1[spos[a[find(apos[i],i)]]];
			++t2[a[find(apos[i],i)]];
		}
		for(register int i=1;i<=st;++i)
		{
			sum+=t1[i];
			sum+=b[apos[r]-1][i]-b[apos[l]][i];
			if(sum>=k)
			{
				sum-=t1[i];
				sum-=b[apos[r]-1][i]-b[apos[l]][i];
				for(register int j=sl[i];j<=sr[i];j++)
				{
					sum+=t2[j];
					sum+=c[apos[r]-1][j]-c[apos[l]][j];
					if(sum>=k)
					{
						ans=j;
						break;
					}
				}
				break;
			}
		}
		for(register int i=l;i<=ar[apos[l]];++i)
		{
			--t1[spos[a[find(apos[i],i)]]];
			--t2[a[find(apos[i],i)]];
		}
		for(register int i=al[apos[r]];i<=r;++i)
		{
			--t1[spos[a[find(apos[i],i)]]];
			--t2[a[find(apos[i],i)]];
		}
	}
	return ans;
}
inline void modify(int l,int r,int x,int y)
{
	for(register int i=at;i>=2;--i)
	{
		b[i][spos[x]]-=b[i-1][spos[x]];
		b[i][spos[y]]-=b[i-1][spos[y]];
		c[i][x]-=c[i-1][x];
		c[i][y]-=c[i-1][y];
	}
	if(apos[l]==apos[r])
	{
		for(register int i=al[apos[l]];i<=ar[apos[l]];++i)
		{
			rt[apos[i]][a[i]]=0;
			a[i]=a[find(apos[i],i)];
			rt[apos[i]][a[i]]=0;
		}
		for(register int i=l;i<=r;++i)
		{
			if(a[i]==x)
			{
				a[i]=y;
				--b[apos[l]][spos[x]];
				++b[apos[l]][spos[y]];
				--c[apos[l]][x];
				++c[apos[l]][y];
			}
		}
   	 	for(register int i=al[apos[l]];i<=ar[apos[l]];++i)
	    {
	    	fa[apos[l]][i]=i;
	    	if(rt[apos[l]][a[i]])
	    	{
	    		fa[apos[l]][i]=rt[apos[l]][a[i]];
			}
			else
			{
				rt[apos[l]][a[i]]=i;
			}
	    }
	}
	else
	{
		for(register int i=al[apos[l]];i<=ar[apos[l]];++i)
		{
			rt[apos[i]][a[i]]=0;
			a[i]=a[find(apos[l],i)];
			rt[apos[i]][a[i]]=0;
		}
		for(register int i=l;i<=ar[apos[l]];++i)
		{
			if(a[i]==x)
			{
				a[i]=y;
				--b[apos[l]][spos[x]];
				++b[apos[l]][spos[y]];
				--c[apos[l]][x];
				++c[apos[l]][y];
			}
		}
   	 	for(register int i=al[apos[l]];i<=ar[apos[l]];i++)
	    {
	    	fa[apos[l]][i]=i;
	    	if(rt[apos[l]][a[i]])
	    	{
	    		fa[apos[l]][i]=rt[apos[l]][a[i]];
			}
			else
			{
				rt[apos[l]][a[i]]=i;
			}
	    }
		for(register int i=apos[l]+1;i<=apos[r]-1;++i)
		{
			if(c[i][x]==0)
			{
				continue;
			}
			else if(c[i][y]==0)
			{
				a[rt[i][x]]=y;
				rt[i][y]=rt[i][x];
				rt[i][x]=0;
				b[i][spos[x]]-=c[i][x];
				b[i][spos[y]]+=c[i][x];
				c[i][y]+=c[i][x];
				c[i][x]=0;
			}
			else
			{
				fa[i][rt[i][x]]=rt[i][y];
				rt[i][x]=0;
				b[i][spos[x]]-=c[i][x];
				b[i][spos[y]]+=c[i][x];
				c[i][y]+=c[i][x];
				c[i][x]=0;
			}
		}
		for(register int i=al[apos[r]];i<=ar[apos[r]];++i)
		{
			rt[apos[i]][a[i]]=0;
			a[i]=a[find(apos[r],i)];
			rt[apos[i]][a[i]]=0;
		}
		for(register int i=al[apos[r]];i<=r;++i)
		{
			if(a[i]==x)
			{
				a[i]=y;
				--b[apos[r]][spos[x]];
				++b[apos[r]][spos[y]];
				--c[apos[r]][x];
				++c[apos[r]][y];
			}
		}
   	 	for(register int i=al[apos[r]];i<=ar[apos[r]];++i)
	    {
	    	fa[apos[r]][i]=i;
	    	if(rt[apos[r]][a[i]])
	    	{
	    		fa[apos[r]][i]=rt[apos[r]][a[i]];
			}
			else
			{
				rt[apos[r]][a[i]]=i;
			}
	    }
	}
	for(register int i=2;i<=at;++i)
	{
		b[i][spos[x]]+=b[i-1][spos[x]];
		b[i][spos[y]]+=b[i-1][spos[y]];
		c[i][x]+=c[i-1][x];
		c[i][y]+=c[i-1][y];
	}
}
int main()
{
    n=read(),m=read();
    Max=0;
    for(register int i=1;i<=n;++i)
    {
        a[i]=read();
        Max=max(Max,a[i]);
    }
    init();
    while(m--)
    {
        int opt,l,r,x,y;
        opt=read(),l=read(),r=read(),x=read();
        if(opt==1)
        {
        	y=read();
        	if(x==y)
        	{
        		continue;
			}
        	modify(l,r,x,y);
		}
		else
		{
			write(kth(l,r,x));
		}
    }
}