第 7 个点 T，1.08s

#include<cstdio>
#define ri register int
#define il inline
#define N 100005
#define NN 167
#define _ 600

#define N2 143
#define _2 700



int n,m,a[N],va[N],p[N],cnt[N],cnt2[N2];
struct kuai{
	int v[N2],va[N],vc[N2],vac[N];
	int r[N]; 
}k[NN];
il void reco(){
	for(ri i=0;i<NN;i++)k[0].vc[i]=k[0].v[i];
	for(ri i=0;i<N;i++)k[0].vac[i]=k[0].va[i];
	for(ri i=1;i<NN;i++){
		for(ri j=0;j<NN;j++)k[i].vc[j]=k[i-1].vc[j]+k[i].v[j];
		for(ri j=0;j<N;j++)k[i].vac[j]=k[i-1].vac[j]+k[i].va[j];
	}
}
il void recoo(ri x,ri y){
	k[0].vc[x/_2]=k[0].v[x/_2];
	k[0].vc[y/_2]=k[0].v[y/_2];
	k[0].vac[x]=k[0].va[x];
	k[0].vac[y]=k[0].va[y];
	for(ri i=1;i<NN;i++){
		k[i].vc[x/_2]=k[i].v[x/_2]+k[i-1].vc[x/_2];
		k[i].vc[y/_2]=k[i].v[y/_2]+k[i-1].vc[y/_2];
		k[i].vac[x]=k[i].va[x]+k[i-1].vac[x];
		k[i].vac[y]=k[i].va[y]+k[i-1].vac[y];
	}
}
il int qu(ri now){
	if(p[now]!=now)p[now]=qu(p[now]);
	return p[now];
}
bool bb[100005],b2[100005];
il void rebuild(ri id,ri x,ri y,ri l,ri r){//printf("(%d %d %d)",id,l,r);
	if(l>r||(!k[id].va[x]))return;
	//if(!k[id].r[x])return;
	k[id].v[x/_2]-=k[id].va[x];
	k[id].va[x]=k[id].r[x]=0;
	for(ri i=id*_;i<(id+1)*_&&i<=n;i++){
		if(va[qu(i)]==x&&i>=l&&i<=r)bb[i]=1;
		else if(va[qu(i)]==x)b2[i]=1;
	}
	for(ri i=id*_;i<(id+1)*_&&i<=n;i++){
		if(bb[i]){
			if(!k[id].r[y])k[id].r[y]=i,va[i]=y;
			p[i]=k[id].r[y];
			k[id].v[y/_2]++;
			k[id].va[y]++;
			bb[i]=0;
		}
		else if(b2[i]){
			if(!k[id].r[x])k[id].r[x]=i,va[i]=x;
			p[i]=k[id].r[x];
			k[id].v[x/_2]++;
			k[id].va[x]++;
			b2[i]=0;
		}
	}
}
il void read(int &a)
{
	a=0;char c;
	while((c=getchar())<48);
	do a=(a<<3)+(a<<1)+(c^48);
	while((c=getchar())>47);
}
il void write(ri x)
{
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
il void gor(ri ll,ri rr,ri x,ri y){
	for(ri i=ll;i<=rr;i++){
		if(!k[i].r[x])continue;
		if(k[i].r[y])p[k[i].r[x]]=k[i].r[y];
		else k[i].r[y]=k[i].r[x],va[k[i].r[y]]=y;
		k[i].r[x]=0;
		ri tt=k[i].va[x];
		k[i].v[x/_2]-=tt;
		k[i].va[x]-=tt;
		k[i].v[y/_2]+=tt;
		k[i].va[y]+=tt;
	}
}
int main(){
// 	freopen("in.txt","r",stdin);
// 	freopen("1.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;i++){
		read(a[i]);
		int nowk=i/_,kn=a[i]/_2;
		k[nowk].va[a[i]]++;
		k[nowk].v[kn]++;
		if(!k[nowk].r[a[i]]) k[nowk].r[a[i]]=i,va[i]=a[i];
		p[i]=k[nowk].r[a[i]];
	}
	reco();
	while(m--){
		ri op,l,r,K,x,y;
		read(op),read(l),read(r);
		if(op==2){
			read(K);
			bool b=0;
			ri ll=-1,rr=-1;
			for(ri i=l;i<=r;i++){
				if(i%_==0){
					ll=i/_;
					break;
				}
				//printf("^%d",va[qu(i)]);
				cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_2]++;
				if(i==r)b=1;
			}
			if(!b)for(ri i=r;i>=l;i--){
				if((i+1)%_==0){
					rr=i/_;
					break;
				} 
				cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_2]++;
			}
			if((ll==-1||rr==-1)||ll>rr){
				ri dd=0,sum=0;
				for(ri i=0;i<N2;i++){
					if(sum+cnt2[i]>=K)break;
					sum+=cnt2[i];dd+=_2;
				}
				for(;;dd++){
					if(sum+cnt[dd]>=K){
						write(dd);
						break;
					}
					sum+=cnt[dd];
				}
			}
			else{
				ri dd=0,sum=0;
				for(ri i=0;i<N2;i++){
					if(sum+cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i]>=K)break;
					sum+=cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i];dd+=_2;
				}
				for(;;dd++){
					if(sum+cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd]>=K){
						write(dd);
						break;
					}
					sum+=cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd];
				}
			}
			for(ri i=l;i<=r;i++){
				if(i%_==0)break;
				cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_2]=0;
			}
			if(!b)for(ri i=r;i>=l;i--){
				if((i+1)%_==0)break;
				cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_2]=0;
			}
			putchar('\n');
		}
		else{
			read(x),read(y);
			if(x==y)continue;
			ri ll=(l-1)/_+1,rr=(r+1)/_-1;
			if(ll>rr+1){
				if(k[rr+1].r[x])rebuild(rr+1,x,y,l,r),recoo(x,y);
				continue;
			}
			if((ll>1&&k[rr+1].vac[x]-k[ll-2].vac[x])||(ll==1&&k[rr+1].vac[x])){
				rebuild(ll-1,x,y,l,ll*_-1);
				rebuild(rr+1,x,y,(rr+1)*_,r);
				gor(ll,rr,x,y);
				recoo(x,y);
			}
			
		}
	}
}