Rt，求助卡常。

亲测同一份代码同一个测试点的时间波动有 500ms（

#include<cstdio>

#define min(a, b) (a < b ? a : b)
#define rep(i, a, b) for(register int i = (a);i <= (b);i++)
#define pre(i, a, b) for(register int i = (a);i >= (b);i--)
#define rp(i, a) for(register int i = 1; i <= (a); i++)
#define pr(i, a) for(register int i = (a); i >= 1; i--)

using namespace std;
char buf[1<<22],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x = 0;char ch = getchar();
    while(ch > '9' || ch < '0')ch = getchar();
    while(ch <= '9' && ch >= '0')x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

#define N 100005
#define M 320

int n, m, t, a[M][M], b[M][N], u[N], v[N], id[M][N], idx[M], mat[M][M], w[M][M], fa[M][M], c[N], s[M], rt[N], tag[M], vs[M], it[N];
inline void clear(int x){
	if(!tag[x])return;
	register int op = 0, y, z, w, L = (x - 1) * 316 + 1, R = min(n, x * 316);
	op = 0;
	rep(i, L, R){
		if(!rt[u[i]])rt[u[i]] = ++op;
		z = y = rt[u[i]];
		if(!vs[y]){
			while(fa[x][z] != z)z = fa[x][z];
			vs[z] = 1;
			while(z != y)w = fa[x][y], vs[y] = 1, fa[x][y] = z, y = w;
		}
		v[i] = mat[x][fa[x][rt[u[i]]]];
	}
	rep(i, L, R)rt[u[i]] = 0, u[i] = v[i];
	rp(i, idx[x])fa[x][i] = id[x][mat[x][i]] = 0, mat[x][i] = vs[i] = 0;
	idx[x] = tag[x] = 0;
	rep(i, L, R)
		if(!id[x][u[i]])id[x][u[i]] = ++idx[x], mat[x][idx[x]] = u[i], fa[x][idx[x]] = idx[x];
}
inline void modify(int x, int &sum, int l, int r, int sx, int sy){
	register int op = 0, y, z, w, L = (x - 1) * 316 + 1, R = min(n, x * 316);
	if(tag[x]){
		op = 0;
		rep(i, L, R){
			if(!rt[u[i]])rt[u[i]] = ++op;
			z = y = rt[u[i]];
			if(!vs[y]){
				while(fa[x][z] != z)z = fa[x][z];
				vs[z] = 1;
				while(z != y)w = fa[x][y], vs[y] = 1, fa[x][y] = z, y = w;
			}
			v[i] = mat[x][fa[x][rt[u[i]]]];
		}
		rep(i, L, R)rt[u[i]] = 0, u[i] = v[i];
		tag[x] = 0;
	}
	rp(i, idx[x])fa[x][i] = id[x][mat[x][i]] = 0, mat[x][i] = vs[i] = 0;
	rep(i, l, r)if(u[i] == sx)u[i] = sy, sum++;
	idx[x] = 0;
	rep(i, L, R)
		if(!id[x][u[i]])id[x][u[i]] = ++idx[x], mat[x][idx[x]] = u[i], fa[x][idx[x]] = idx[x];
}
inline void query(){
	int l = read(), r = read(), k = read();
	//cout << l << " " << r << " " << k << endl;
	int ll = it[l], rr = it[r];
	if(ll == rr){
		
		clear(ll);//cout<<"cc "<<endl;
		rep(i, l, r)c[u[i]]++, s[it[u[i]]] ++;
		register int j = 1;
		while(true){
			if(s[j] < k)k -= s[j++];
			else break;
		}
		j = j *316 - 315;
		while(true){
			if(c[j] >= k){printf("%d\n", j);break;}
			k -= c[j++];
		}
		rep(i, l, r)c[u[i]] = 0, s[it[u[i]]] = 0;
		return;
	}
	clear(ll), clear(rr);
	int L = ll * 316, R = rr * 316 - 315;
	//cout << L << " " << R << endl; 
	rep(i, l, L)c[u[i]]++, s[it[u[i]]] ++;
	rep(i, R, r)c[u[i]]++, s[it[u[i]]] ++;
	register int j = 1, cur;
	while(true){
		cur = a[rr - 1][j] - a[ll][j] + s[j];
		if(cur < k) k -= cur, j++;
		else break;
	}
	j = j * 316 - 315;
	while(true){
		cur = c[j] + b[rr - 1][j] - b[ll][j];
		if(cur >= k){printf("%d\n", j);break;}
		k -= cur, j ++ ;
	}
	rep(i, l, L)c[u[i]] = 0, s[it[u[i]]] = 0;
	rep(i, R, r)c[u[i]] = 0, s[it[u[i]]] = 0;
}
inline void change(){
	int l = read(), r = read(), x = read(), y = read();
	if(x == y)return;
	int ll = it[l], rr = it[r];
	if(ll == rr){
		int w = 0; modify(ll, w, l, r, x, y);
		pre(i, it[n], ll)
			a[i][it[x]] -= w, a[i][it[y]] += w, b[i][x] -= w, b[i][y] += w;
		return;
	}
	//ins(ll, l, ll * p, x, y), 
	//ins(rr, (rr - 1) * p + 1, r, x, y);
	register int sum = 0, lst = b[ll][x];
	modify(ll, sum, l, ll * 316, x, y);
	a[ll][it[x]] -= sum, a[ll][it[y]] += sum, b[ll][x] -= sum, b[ll][y] += sum;
	rep(i, ll + 1, rr - 1){
		if(id[i][x]){
			sum += b[i][x] - lst;
			if(id[i][y])
				fa[i][id[i][x]] = id[i][y], mat[i][id[i][x]] = 0, id[i][x] = 0;
			else mat[i][id[i][x]] = y, id[i][y] = id[i][x], id[i][x] = 0;
			tag[i] = 1;
		}
		lst = b[i][x], a[i][it[x]] -= sum, a[i][it[y]] += sum, b[i][x] -= sum, b[i][y] += sum;
	}
	modify(rr, sum, rr * 316 - 315, r, x, y);
	pre(i, it[n], rr)
		a[i][it[x]] -= sum, a[i][it[y]] += sum, b[i][x] -= sum, b[i][y] += sum;
}
int main(){
	n = read(), t = read(), m = 100000;
	register int x, k = (m - 1) / 316 + 1;
	rp(i, n){
		u[i] = read(), x = it[i] = (i - 1) / 316 + 1;
		if(!id[x][u[i]])id[x][u[i]] = ++idx[x], mat[x][idx[x]] = u[i], fa[x][idx[x]] = idx[x];
		if((i - 1) % 316 == 0){
			rp(j, k)a[x][j] = a[x - 1][j];
			rp(j, m)b[x][j] = b[x - 1][j];
		}
		a[x][(u[i] - 1) / 316 + 1]++, b[x][u[i]]++;
	}
	while(t--){
		if(1 == read())change();
		else query();
	}
	return 0;
}