分块套权值线段树（先不管复杂度对不对）。在 IDE 上显示空间超限，数组有大约 300MB。本地构造的最大数据都可以跑，但是提交就全部 RE。求助。

#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <array>
#include <bitset>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define b_e(a) a.begin(),a.end()
#define F(i,a,b) for(i=a;i<=(b);++i)
#define G(i,a,b) for(i=a;i>=(b);--i)
#define R(i,a,b) for(i=a;i<(b);++i)
#define P(i,a,b) for(i=a;i>(b);--i)
typedef signed char i8;typedef unsigned char u8;
typedef short i16;typedef unsigned short u16;
typedef int i32;typedef unsigned u32;
typedef long long i64;typedef unsigned long long u64;
typedef float f32;typedef double f64;
namespace _ns{
	template<typename T>T& max(T& a,T& b){return a>b?a:b;}
	template<typename T,typename... A>T& max(T& a,T& b,A& ...c){return max(a=max(a,b),c...);}
	template<typename T>T& min(T& a,T& b){return a<b?a:b;}
	template<typename T,typename... A>T& min(T& a,T& b,A& ...c){return min(a=min(a,b),c...);}
	const u32 buf_s(1<<14);bool ne;char i[buf_s],*ib(i),*ie(i),o[buf_s],*ob(o),a[20],&c(*a),*b;const char *oe(o+buf_s);
	bool check(){return ~c&&c!=' '&&c!='\r'&&c!='\n';}
	void n(){c=(ib==ie&&(ie=(ib=i)+fread(i,1,buf_s,stdin),ib==ie)?-1:*ib);}
	void f(){ob-=fwrite(o,1,ob-o,stdout);}
	void p(char c){if(ob==oe)f();*ob++=c;}
	void r(char& r){for(n();!check();++ib,n());r=c;++ib;n();}
	void r(i8& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
	void r(i16& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
	void r(int& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
	void r(i64& r){r=ne=false;for(n();c<'0'||c>'9';++ib,n())ne=(c=='-');for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');if(ne)r=~(r-1);}
	void r(u8& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
	void r(u16& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
	void r(u32& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
	void r(u64& r){r=0u;for(n();c<'0'||c>'9';++ib,n());for(;'0'<=c&&c<='9';++ib,n())r=(r<<3)+(r<<1)+(c^'0');}
	void r(char* s){for(n();!check();++ib)n();for(*s++=c,n();check();++ib,n())*s++=c;*s=0;}
	void r(std::string& s){s.clear();for(n();!check();++ib,n());for(s.push_back(c),++ib,n();check();++ib,n())s.push_back(c);}
	void w(char r){p(r);}void w(char* s){for(;*s;p(*s++));}
	void w(const char* s){for(;*s;p(*s++));}
	void w(std::string s){w(s.data());}
	void w(i8 r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(i16 r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(int r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(i64 r){if(r==0)return p('0');if(r<0)p('-'),r=~(r-1);for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(u8 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(u16 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(u32 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	void w(u64 r){if(r==0)return p('0');for(b=a;r!=0;r/=10)*++b=(r%10)^'0';for(;b!=a;)p(*b--);}
	template<typename T>void write(T& a){_ns::w(a);}
	template<typename T,typename... A>void write(T& a,A&... b){write(a);write(b...);}
	struct end_of_program{~end_of_program(){f();}}eop;
}
template<typename... A>void debug(A ...a){fprintf(stderr,a...);fflush(stderr);}
template<typename T,typename... A>T max(T a,A ...b){return _ns::max(a,b...);}
template<typename T,typename... A>T min(T a,A ...b){return _ns::min(a,b...);}
template<typename T1,typename T2>void to_max(T1& a,T2 b){if(a<b){a=b;}}
template<typename T1,typename T2>void to_min(T1& a,T2 b){if(b<a){a=b;}}
template<typename T>void read(T& a){_ns::r(a);}void read(char* s){_ns::r(s);}
template<typename T,typename... A>void read(T& a,A&... b){read(a);read(b...);}
template<typename... A>void write(A... a){_ns::write(a...);}

constexpr int A(1e5+5),B(317),C(2e6),D(1e5);
struct dsu{
	int f[A],s[A];
	void init(int n){
		std::iota(f+1,f+n+1,1);
		std::fill(s+1,s+n+1,1);
	}
	int fd(int k){
		return f[k]==k?k:f[k]=fd(f[k]);
	}
	void merge(int u,int v){
		f[fd(u)]=fd(v);
	}
}d[B];
struct node{
	int sum;
	node *ls,*rs;
}t[C],*root[B],*sta[C],**top,*qing[B],**tot;
int n,m,block,a[A],b[A],*tb,pos[A],pl[A],pr[A];

void update(node*& u,int x,int k,int l=1,int r=D){
	if(u==t){
		assert(top>sta);
		u=*--top;
		u->sum=0;
		u->ls=u->rs=t;
	}
	u->sum+=k;
	if(l<r){
		const int mid((l+r)>>1);
		if(x<=mid){
			update(u->ls,x,k,l,mid);
		}else{
			update(u->rs,x,k,mid+1,r);
		}
	}
	if(!u->sum){
		*top++=u;
		u=t;
	}
}
int query(node*& u,int x,int l=1,int r=D){
	if(l==r){
		return u->sum;
	}
	const int mid((l+r)>>1);
	return x<=mid?query(u->ls,x,l,mid):query(u->rs,x,mid+1,r);
}
void push_down(int u){
	int i,l(pl[u]),r(pr[u]);
	memcpy(b+l,a+l,(r-l+1)<<2);
	F(i,l,r){
		a[i]=d[pos[l]].fd(a[i]);
	}
	F(i,l,r){
		d[pos[l]].f[b[i]]=b[i];
	}
}
void modify(int l,int r,int x,int y){
	if(pos[l]==pos[r]){
		push_down(pos[l]);
		std::replace(a+l,a+r+1,x,y);
	}else{
		int i,tmp;
		if(pos[l]==pos[l-1]){
			push_down(pos[l]);
			i=pr[pos[l]];
			std::replace(a+l,a+i+1,x,y);
			l=i+1;
		}
		if(pos[r]==pos[r+1]){
			push_down(pos[r]);
			i=pl[pos[r]];
			std::replace(a+i,a+r+1,x,y);
			r=i-1;
		}
		l=pos[l];r=pos[r];
		F(i,l,r){
			tmp=query(root[i],x);
			if(tmp){
				d[i].merge(x,y);
				update(root[i],x,-tmp);
				update(root[i],y,tmp);
			}
		}
	}
}
int lower_b(int x){
	if(tb==b){
		return 0;
	}
	return std::upper_bound(b,tb,x)-b;
}
int query_kth(int l,int r,int k){
	if(pos[l]==pos[r]){
		push_down(pos[l]);
		memcpy(b+l,a+l,(r-l+1)<<2);
		std::sort(b+l,b+r+1);
		return b[l+k-1];
	}
	int i,x(1),y(D),mid,lsum;
	node** u;
	tot=qing;tb=b;
	if(pos[l]==pos[l-1]){
		push_down(pos[l]);
		i=pr[pos[l]];
		memcpy(tb,a+l,(i-l+1)<<2);
		tb+=i-l+1;
		l=i+1;
	}
	if(pos[r]==pos[r+1]){
		push_down(pos[r]);
		i=pl[pos[r]];
		memcpy(tb,a+i,(r-i+1)<<2);
		tb+=r-i+1;
		r=i-1;
	}
	std::sort(b,tb);
	l=pos[l];r=pos[r];
	memcpy(qing,root+l,(r-l+1)<<3);
	tot+=(r-l+1);
	for(;x<y;){
		mid=(x+y)>>1;
		lsum=0;
		for(u=qing;u!=tot;++u){
			lsum+=(*u)->ls->sum;
		}
		lsum+=lower_b(mid);
		if(k<=lsum){
			for(u=qing;u!=tot;++u){
				*u=(*u)->ls;
			}
			y=mid;
		}else{
			k-=lsum;
			for(u=qing;u!=tot;++u){
				*u=(*u)->rs;
			}
			x=mid+1;
		}
	}
	return x;
}
int main(int argc,char** argv){
	int i,o,l,r,x,y;
	t->sum=0;
	t->ls=t->rs=t;
	read(n,m);
	block=sqrt(n);
	F(i,1,n){
		read(a[i]);
		pos[i]=(i-1)/block+1;
		pr[pos[i]]=i;
	}
	R(i,0,B){
		d[i].init(n);
	}
	std::iota(sta,sta+C-1,t+1);
	top=sta+C-1;
	std::fill(root+1,root+pos[n]+1,t+0);
	G(i,n,1){
		pl[pos[i]]=i;
		update(root[pos[i]],a[i],1);
	}
	F(i,1,m){
		read(o,l,r,x);
		if(o==1){
			read(y);
			continue;
			modify(l,r,x,y);
		}else{
			write(query_kth(l,r,x),'\n');
		}
	}
	return 0;
}