写了一天了，对拍总是和正确答案差一点，现在只想保证正确性，卡常后面再说。

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 500
namespace fast_IO{
	#define FASTIO
	#define IOSIZE 100000
	char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
	#ifdef ONLINE_JUDGE
	#define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
	#define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
	#endif
	#define isdigit(ch)(ch>47&&ch<58)
	#define isspace(ch)(ch<33)
	template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
	#ifdef _GLIBCXX_STRING
	inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
	#endif
	template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}using namespace fast_IO;
#define cin io
#define cout io
#define endl '\n'
namespace cza{
	int n, m, B, lb;
	int a[N];
	int kuai[N], lft[N], rit[N];   //分块 
	int bcnt[M][M], cnt[M][N];     //前i个块中有多少个在第j个值域块中的 / 前i个块中有多少个值为j的 
	int fa[N], v[M][N], re[M][N];  //并查集，v表示第i个块中j对应的值，re表示第i个块中值为j的是谁 
	int get_fa(int u){
		return fa[u] == u ? u : fa[u] = get_fa(fa[u]); 
	}
	void merge(int p, int u, int vv){
		u = get_fa(u), vv = get_fa(vv);
		fa[u] = vv;
		re[p][v[p][u]] = 0;
		v[p][u] = 0;
	}
	void init(){
		B = 420;
		for(int i = 1; i <= N - 10; i++) kuai[i] = (i - 1) / B + 1;
		lb = kuai[N - 10];
		for(int i = 1; i <= lb; i++) lft[i] = rit[i - 1] + 1, rit[i] = i * B;
		rit[lb] = n;
		for(int i = 1; i <= n; i++){
			bcnt[kuai[i]][kuai[a[i]]]++;
			cnt[kuai[i]][a[i]]++;
		}
		for(int i = 1; i <= lb; i++){
			for(int j = 1; j <= lb; j++){
				bcnt[i][j] += bcnt[i - 1][j];
			}
		}
		for(int i = 1; i <= lb; i++){
			for(int j = 1; j <= N - 10; j++){
				cnt[i][j] += cnt[i - 1][j];
			}
		}
		vector<int> tmp;
		for(int i = 1; i <= lb; i++){
			tmp. resize(N);
			tmp. clear();
			for(int j = lft[i]; j <= rit[i]; j++){
				fa[j] = j;
				if(!tmp[a[j]]){
					tmp[a[j]] = j;
					v[i][j] = a[j];
					re[i][a[j]] = j;
				}else{
					merge(i, j, tmp[a[j]]);
				}
			}
		}
	}//预处理 
	void remod(int p){
		for(int i = lft[p]; i <= rit[p]; i++){
			a[i] = v[p][get_fa(i)];
		}//将p块的a数组重新赋值正确 
	}
	void rebuild(int p){
		vector<int> tmp;
		tmp. resize(N);
		tmp. clear();
		for(int j = lft[p]; j <= rit[p]; j++){
			fa[j] = j;
			if(!tmp[a[j]]){
				tmp[a[j]] = j;
				v[p][j] = a[j];
				re[p][a[j]] = j;
			}else{
				merge(p, j, tmp[a[j]]);
			}
		}
	}//重构p块的并查集 
	void change(int l, int r, int x, int y){
		if(x == y) return ;
		int bl = kuai[l], br = kuai[r];
		if(bl == br){
			remod(bl);
			int der = 0;
			for(int i = l; i <= r; i++){
				if(a[i] == x) a[i] = y, der++;
			}
			rebuild(bl);
			for(int i = bl; i <= lb; i++){
				cnt[i][x] -= der;
				cnt[i][y] += der;
				bcnt[i][kuai[x]] -= der;
				bcnt[i][kuai[y]] += der;
			}
			return ;
		}
		remod(bl);
		int der1 = 0;
		for(int i = l; i <= rit[bl]; i++){
			if(a[i] == x) a[i] = y, der1++;
		}
		rebuild(bl);
		remod(br);
		int der2 = 0;
		for(int i = lft[br]; i <= r; i++){
			if(a[i] == x) a[i] = y, der2++;
		}
		rebuild(br);
		for(int i = bl + 1; i < br; i++){
			if(!re[i][x]) continue;
			if(!re[i][y]){
				re[i][y] = re[i][x];
				re[i][x] = 0;
				v[i][re[i][y]] = y; 
			}else{
				merge(i, re[i][x], re[i][y]);
			}
		}
		int der = 0, last = cnt[bl - 1][x];
		for(int i = bl; i <= lb; i++){
			if(i == bl) der += der1;
			else if(i == br) der += der2;
			else if(bl < i and i < br) der += cnt[i][x] - last;
			last = cnt[i][x];
			cnt[i][x] -= der;
			cnt[i][y] += der;
			bcnt[i][kuai[x]] -= der;
			bcnt[i][kuai[y]] += der;
		}//更新 bcnt cnt 
	}
	int R(int p, int x){
		return v[p][get_fa(x)];
	}//x位置的真实值 
	int get_ans(int l, int r, int k){
		int bl = kuai[l], br = kuai[r];
		vector<int> tmp;
		tmp. resize(N);
		tmp. clear();
		vector<int> btmp;
		btmp. resize(N);
		btmp. clear();
		if(bl == br){
			for(int i = l; i <= r; i++){
				tmp[R(bl, i)]++;
				btmp[kuai[R(bl, i)]]++;
			}
			int now = 1;
			int der = btmp[1];
			while(k > der) k -= der, now++, der = btmp[now];
			now = lft[now];
			der = tmp[now];
			while(k > der) k -= der, now++, der = tmp[now];
			return now;
		}
		for(int i = l; i <= rit[bl]; i++){
			tmp[R(bl, i)]++;
			btmp[kuai[R(bl, i)]]++;
		}
		for(int i = lft[br]; i <= r; i++){
			tmp[R(br, i)]++;
			btmp[kuai[R(br, i)]]++;
		}
		int now = 1;
		int der = btmp[now] + bcnt[br - 1][now] - bcnt[bl][now];
		while(k > der) k -= der, now++, der = btmp[now] + bcnt[br - 1][now] - bcnt[bl][now];
		now = lft[now];
		der = tmp[now] + cnt[br - 1][now] - cnt[bl][now];
		while(k > der) k -= der, now++, der = tmp[now] + cnt[br - 1][now] - cnt[bl][now];
		return now;
	}
	int main(){
		cin >> n >> m;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
		}
		init();
		for(int i = 1; i <= m; i++){
			int op, l, r, x, y;
			cin >> op >> l >> r;
			if(op == 1){
				cin >> x >> y;
				change(l, r, x, y);
			}else{
				cin >> x;
				cout << get_ans(l, r, x) << '\n';
			}
		}
		return 0;
	}
}
signed main(){
	return cza::main();
}

代码写得很史
谁来救救我