rt，序列分块套值域分块，问题大概出在修改

/*
维护cnt[i][j]表示前i个序列块有多少个j
维护cnt_B[i][j]表示前i个序列块中有多少个数在第j个值域块

fr[x][y]表示第x个序列块中y第一次出现位置 

*/
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, B = 500;

#define L(i) ((i - 1) * B + 1)
#define R(i) (i != len ? i * B : n)
#define bel(i) ((i - 1) / B + 1) 

int n, len, LEN;
int a[N];
int cnt[N / B + 5][N], cnt_B[N / B + 5][N / B + 5];
int fr[N / B + 5][N], fa[N], sz[N];

//并查集 
int find(int x) {
	while(x ^ fa[x]) x = fa[x] = fa[fa[x]]; return x;
}


void init() {
	len = n / B + !!(n % B), LEN = bel(N - 5);
	for(int b = 1; b <= len; b++) {
		for(int i = 1; i < N; i++) cnt[b][i] += cnt[b - 1][i];
		for(int i = 1; i < N / B + 5; i++) cnt_B[b][i] += cnt_B[b - 1][i];
		for(int i = L(b), ed = R(b); i <= ed; i++) {
			cin>>a[i];
			cnt[b][a[i]]++, cnt_B[b][bel(a[i])]++;
			if(!fr[b][a[i]]) fr[b][a[i]] = i;
			fa[i] = fr[b][a[i]], sz[fa[i]]++;
		}
	}
} 
//标记下传+清空并查集 
void clear(int b, int l, int r) {
	for(int i = r; i >= l; i--) {
		a[i] = a[find(i)], fa[i] = 0;
		if(i == fr[b][a[i]]) sz[fr[b][a[i]]] = 0,fr[b][a[i]] = 0;
	}
}
//散块修改 
void modify_sep(int b, int l, int r, int x, int y, int bx, int by) {
	int st = L(b), ed = R(b), del = 0; 
	for(int i = l; i <= r; i++) del += a[i] == x;
	if(!del) return ;
	clear(b, st, ed);
	for(int i = st; i < l; i++) {
		if(!fr[b][a[i]]) fr[b][a[i]] = i;
		fa[i] = fr[b][a[i]], sz[fa[i]]++;
	}
	for(int i = l; i <= r; i++) {
		if(a[i] == x) a[i] = y;
		if(!fr[b][a[i]]) fr[b][a[i]] = i;
		fa[i] = fr[b][a[i]], sz[fa[i]]++;
	}
	for(int i = r + 1; i <= ed; i++) {
		if(!fr[b][a[i]]) fr[b][a[i]] = i;
		fa[i] = fr[b][a[i]], sz[fa[i]]++;
	}
	for(int i = b; i <= len; i++) 
		cnt[i][x] -= del, cnt[i][y] += del, 
		cnt_B[i][bx] -= del, cnt_B[i][by] += del;
}
//修改 
void modify(int l, int r, int x, int y) {
	if(x == y) return ;
	int bl = bel(l), br = bel(r), bx = bel(x), by = bel(y);
	if(bl == br) return modify_sep(bl, l, r, x, y, bx, by);
	modify_sep(bl, l, R(bl), x, y, bx, by), bl++;
	modify_sep(br, L(br), r, x, y, bx, by), br--;
	//整块 
	for(int i = bl, pre = 0; i <= br; i++) {
		fr[i][x] = find(fr[i][x]), fr[i][y] = find(fr[i][y]);
		if(fr[i][x]) {
			if(fr[i][y]) {
				pre += sz[fr[i][x]];
				sz[fr[i][y]] += sz[fr[i][x]], sz[fr[i][x]] = 0;
				fa[fr[i][x]] = fr[i][y];
			} else a[fr[i][x]] = y, swap(fr[i][x], fr[i][y]);
		}
		cnt[i][x] -= pre, cnt[i][y] += pre;
		cnt_B[i][bx] -= pre, cnt_B[i][by] += pre;
	}
}

int sep[B * 2 + 5], csep;
int qry(int l, int r, int k) {
//	cout<<k<<'\n';
	int bl = bel(l), br = bel(r); csep = 0;
	if(br - bl < 2) {
		for(int i = l; i <= r; i++) sep[++csep] = a[find(i)];
		sort(sep + 1, sep + 1 + csep); //cout<<"KKK";
		return sep[k];
	}
	for(int i = l, ed = R(bl); i <= ed; i++) sep[++csep] = a[find(i)]; bl++;
	for(int i = L(br); i <= r; i++) sep[++csep] = a[find(i)]; br--;
	sort(sep + 1, sep + 1 + csep);
	int bel_B = LEN, pre = 0, psep = 0;
	for(int b = 1, rg, del, delp; b <= LEN; b++) {
		rg = b * B, del = delp = 0;
		while(psep + delp < csep && sep[psep + delp + 1] <= rg) delp++;
		del += cnt_B[br][b] - cnt_B[bl - 1][b];
//		cout<<pre+psep+del+delp<<'\n';
		if(pre + psep + del + delp >= k) { bel_B = b; break; }
		pre += del, psep += delp;
	} 
	for(int i = (bel_B - 1) * B + 1, ed = bel_B * B; i <= ed; i++) {
		while(psep < csep && sep[psep + 1] <= i) psep++;
		pre += cnt[br][i] - cnt[bl - 1][i];
//		cout<<pre+psep<<'\n';
		if(pre + psep >= k) return i;
	}
	return 114514;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//	freopen("data.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	int QWQ;
	cin>>n>>QWQ; 
	init();
	for(int op, l, r, x, y; QWQ; QWQ--) {
		cin>>op>>l>>r>>x;
		if(op == 1) {
			cin>>y, modify(l, r, x, y);
		} else {
			cout<<qry(l, r, x)<<'\n';
		}
//		if(op == 1) {
//			for(int i = 1; i <= n; i++) {
//				cout<<a[find(i)]<<' ';
//			} cout<<'\n';
//		}
	}
	
	return 0;
}