瓦9个点10pt求调

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
template<typename Tp> Tp read() {
	Tp x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
template<typename Tp> void write(Tp x) {
	if(x<0) {putchar('-');x=-x;}
	static int sta[45];int top=0;
	do {sta[top++]=x%10;x/=10;} while(x);
	while(top) putchar(sta[--top]+'0');
}
constexpr int N=1e5+5,B=170,SZ=600,S=320,VSZ=320,MAXV=1e5;
int n,m,a[N],k,le[B],ri[B],cnt[B][N],sumc[B][N],vbel[N],sums[B][S],c[N],s[S];
int fa[N],rt[B][N];
int find(int x) {
	return x==fa[x]?x:x=find(fa[x]);
}
int sta[N],top;
void update(int p,int l,int r,int x,int y) {
	int tmp=0;top=0;
	rt[p][x]=rt[p][y]=0;
	for(int i=le[p];i<=ri[p];i++) {
		a[i]=a[find(i)];
		if(a[i]==x||a[i]==y) sta[++top]=i;
	}
	for(int i=l;i<=r;i++)
		if(a[i]==x) a[i]=y,tmp++;
	for(int i=1;i<=top;i++) fa[sta[i]]=sta[i];
	for(int i=1;i<=top;i++) {
		if(!rt[p][a[sta[i]]]) rt[p][a[sta[i]]]=sta[i];
		else fa[sta[i]]=rt[p][a[sta[i]]];
	}
	cnt[p][x]-=tmp,cnt[p][y]+=tmp;
	for(int i=p;i<=k;i++) {
		sumc[i][x]-=tmp,sumc[i][y]+=tmp;
		if(vbel[x]!=vbel[y]) sums[i][vbel[x]]-=tmp,sums[i][vbel[y]]+=tmp;
	}
}
int main() {
	n=read<int>(),m=read<int>();
	k=(n-1)/SZ+1;
	for(int i=1;i<=n;i++) a[i]=read<int>(),fa[i]=i;
	for(int i=1;i<=MAXV;i++) vbel[i]=(i-1)/VSZ+1;
	for(int i=1;i<=k;i++) {
		le[i]=(i-1)*SZ+1,ri[i]=min(i*SZ,n);
		for(int j=le[i];j<=ri[i];j++) {
			if(!rt[i][a[j]]) rt[i][a[j]]=j;
			else fa[j]=rt[i][a[j]];
			cnt[i][a[j]]++;
		}
		for(int j=1;j<=MAXV;j++) sumc[i][j]=sumc[i-1][j]+cnt[i][j];
		for(int j=1;j<S;j++) sums[i][j]=sums[i-1][j];
		for(int j=le[i];j<=ri[i];j++) sums[i][vbel[a[j]]]++;
	}
	while(m--) {
		int op=read<int>();
		if(op==1) {
			int l=read<int>(),r=read<int>(),x=read<int>(),y=read<int>();
			if(x==y) continue;
			int lb=(l-1)/SZ+1,rb=(r-1)/SZ+1;
			if(lb==rb) update(lb,l,r,x,y);
			else {
				update(lb,l,ri[lb],x,y);
				update(rb,le[rb],r,x,y);
				int tmp=0;
				for(int i=lb+1;i<rb;i++) {
					if(rt[i][x]) {
						if(!rt[i][y]) rt[i][y]=rt[i][x];
						else fa[rt[i][x]]=rt[i][y];
						rt[i][x]=0,tmp+=cnt[i][x];
						cnt[i][y]+=cnt[i][x],cnt[i][x]=0;
					}
					sumc[i][x]-=tmp,sumc[i][y]+=tmp;
					if(vbel[x]!=vbel[y]) sums[i][vbel[x]]-=tmp,sums[i][vbel[y]]+=tmp;
				}
				for(int i=rb;i<=k;i++) {
					sumc[i][x]-=tmp,sumc[i][y]+=tmp;
					if(vbel[x]!=vbel[y]) sums[i][vbel[x]]-=tmp,sums[i][vbel[y]]+=tmp;
				}
			}
		}
		else {
			int l=read<int>(),r=read<int>(),x=read<int>();
			int lb=(l-1)/SZ+1,rb=(r-1)/SZ+1;
			if(lb==rb) {
				for(int i=l;i<=r;i++)
					a[i]=a[find(i)],c[a[i]]++,s[vbel[a[i]]]++;
				int vl=-1,vr=-1,tmp=0;
				for(int i=1;i<S;i++) {
					tmp+=s[i];
					if(tmp>=x) {
						tmp-=s[i];
						vl=(i-1)*VSZ+1,vr=i*VSZ;
						break;
					}
				}
				for(int i=vl;i<=vr;i++) {
					tmp+=c[i];
					if(tmp>=x) {
						write(i);putchar('\n');
						break;
					}
				}
				for(int i=l;i<=r;i++)
					c[a[i]]--,s[vbel[a[i]]]--;
			}
			else {
				for(int i=l;i<=ri[lb];i++)
					a[i]=a[find(i)],c[a[i]]++,s[vbel[a[i]]]++;
				for(int i=le[rb];i<=r;i++)
					a[i]=a[find(i)],c[a[i]]++,s[vbel[a[i]]]++;
				int vl=-1,vr=-1,tmp=0;
				for(int i=1;i<S;i++) {
					tmp+=s[i]+sums[rb-1][i]-sums[lb][i];
					if(tmp>=x) {
						tmp-=s[i]+sums[rb-1][i]-sums[lb][i];
						vl=(i-1)*VSZ+1,vr=i*VSZ;
						break;
					}
				}
				for(int i=vl;i<=vr;i++) {
					tmp+=c[i]+sumc[rb-1][i]-sumc[lb][i];
					if(tmp>=x) {
						write(i);putchar('\n');
						break;
					}
				}
				for(int i=l;i<=ri[lb];i++)
					c[a[i]]--,s[vbel[a[i]]]--;
				for(int i=le[rb];i<=r;i++)
					c[a[i]]--,s[vbel[a[i]]]--;
			}
		}
	}
	return 0;
}