做了一天了，把几乎除了满分以外的分都得过了，这是91pts中最快的：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n,m,cblo,op,x,y,z,w,a[100010],tmp1[320],tmp[100010],s[320][100010],s1[320][320],sum[320][100010],st[320],ed[320],bel[100010],bel1[100010],sum1[320][320],fa[100010],fl[320][100010];const int blo=550; 
inline int read(){
	register int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while('0'<=c&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}
inline void write(int x) {
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
	return;
}
inline int find(register int x){
	if(x==fa[x])return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
inline void chg(register int x,register int y,register int z){
	--sum[x][y];++sum[x][z];
	--sum1[x][bel1[y]];++sum1[x][bel1[z]];
}
inline void build(register int id,register int x){
	for(register int i=id;i<=cblo;++i)s[i][x]=s[i-1][x]+sum[i][x];
	for(register int i=id;i<=cblo;++i)s1[i][bel1[x]]=s1[i-1][bel1[x]]+sum1[i][bel1[x]];
}
inline void modify(register int l,register int r,register int x,register int y){
	for(register int i=st[bel[l]];i<=ed[bel[l]];++i)a[i]=a[find(i)]; 
	fl[bel[l]][x]=fl[bel[l]][y]=0;
	for(register int i=l;i<=r;++i){
		if(a[i]==x){
			a[i]=y;chg(bel[l],x,y);
		}
	}
	for(register int i=st[bel[l]];i<=ed[bel[l]];++i){
		if(a[i]!=x&&a[i]!=y)continue;
		if(fl[bel[l]][a[i]])fa[i]=fl[bel[l]][a[i]];
		else{
			fl[bel[l]][a[i]]=i;fa[i]=i;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	n=read();m=read();cblo=(n+blo-1)/blo;
	for(register int i=1;i<=n;++i)a[i]=read();
	for(register int i=1;i<=cblo;++i){
		st[i]=(i-1)*blo+1;ed[i]=i*blo;
	}
	for(register int i=1;i<=n;++i){
		bel[i]=(i+blo-1)/blo;
	}
	for(register int i=1;i<=100000;++i){
		bel1[i]=(i+blo-1)/blo;
	}
	for(register int i=1;i<=n;++i)fa[i]=i;
	ed[cblo]=n;
	for(register int i=1;i<=n;++i){
		sum[bel[i]][a[i]]++;sum1[bel[i]][bel1[a[i]]]++;
	}
	for(register int i=1;i<=cblo;++i){
		for(register int j=st[i];j<=ed[i];++j){
			if(fl[i][a[j]])fa[j]=fl[i][a[j]];
			else{
				fl[i][a[j]]=j;fa[j]=j;
			}
		}
	}
	for(register int i=1;i<=100000;++i)build(1,i);
	while(m--){
		op=read();x=read();y=read();z=read();
		if(op==1){
			w=read();
			if(z==w)continue;
			if(bel[x]==bel[y]){
				modify(x,y,z,w);build(bel[x],z);build(bel[x],w);continue;
			}
			modify(x,st[bel[x]+1]-1,z,w);
			modify(ed[bel[y]-1]+1,y,z,w);
			for(register int i=bel[x]+1;i<bel[y];++i){
				if(!fl[i][z])continue;
				if(!fl[i][w]){
					a[fl[i][z]]=w;fl[i][w]=fl[i][z];
				}
				else fa[fl[i][z]]=fl[i][w];
				sum1[i][bel1[w]]+=sum[i][z];
				sum1[i][bel1[z]]-=sum[i][z];
				sum[i][w]+=sum[i][z];sum[i][z]=fl[i][z]=0;
			}
			build(bel[x],z);build(bel[x],w);
		}
		else{
			if(bel[x]==bel[y]){
				for(register int i=x;i<=y;++i){
					++tmp1[bel1[a[find(i)]]];
					++tmp[a[find(i)]];
				}
			}
			else{
				for(register int i=x;i<=st[bel[x]+1]-1;++i){
					++tmp1[bel1[a[find(i)]]];
					++tmp[a[find(i)]];
				}
				for(register int i=ed[bel[y]-1]+1;i<=y;++i){
					++tmp1[bel1[a[find(i)]]];
					++tmp[a[find(i)]];
				}
				for(register int i=1;i<=182;++i)tmp1[i]+=s1[bel[y]-1][i]-s1[bel[x]][i];
			}
			for(register int i=1;i<=182;++i){
				if(z<=tmp1[i]){
					for(register int j=(i-1)*blo+1;j<=i*blo;++j){
						if(bel[x]!=bel[y]){
							if(z<=tmp[j]+s[bel[y]-1][j]-s[bel[x]][j]){
								cout<<j<<"\n";break;
							}
							else z-=tmp[j]+s[bel[y]-1][j]-s[bel[x]][j];
						}
						else{
							if(z<=tmp[j]){
								cout<<j<<"\n";break;
							}
							else z-=tmp[j];
						}
					}
					break;
				}
				else z-=tmp1[i];
			}
			if(bel[x]==bel[y]){
				for(register int i=x;i<=y;++i){
					--tmp1[bel1[a[find(i)]]];
					--tmp[a[find(i)]];
				}
			}
			else{
				for(register int i=x;i<=st[bel[x]+1]-1;++i){
					--tmp1[bel1[a[find(i)]]];
					--tmp[a[find(i)]];
				}
				for(register int i=ed[bel[y]-1]+1;i<=y;++i){
					--tmp1[bel1[a[find(i)]]];
					--tmp[a[find(i)]];
				}
				for(register int i=1;i<=182;++i)tmp1[i]-=s1[bel[y]-1][i]-s1[bel[x]][i];
			}
		}
	}
	return 0;
}
/*
17 3
4 4 1 5 4 5 4 3 1 1 2 2 1 3 2 5 2
1 5 11 4 3
1 5 11 1 4
2 8 11 3

4
*/