rt，树状数组套主席树，主席树数组 a 开小了 $(<9\times 10^6)$ 会 RE+WA，主席树开大了 $\ge 9\times 10^6$ 会 MLE。但是经过计算即使主席树数组开 $4\times 10^7$ 也不会 MLE。
目前的想法是主席树到叶子结点以后继续往下延伸，或者多开了没用的点。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,b[100005],h[200005],tot,rt[200015],jia[100005],jian[100005];
struct node{
	int num,ls,rs;
}a[40000005];//指的是这个数组
struct NODE{
	char op;
	int l,r,k;
}cz[100005];
int build(int l,int r){
	int now;
	now = ++cnt;
	if(l == r){
		return now; 
	}
	int mid;
	mid = (l+r)/2;
	a[now].ls = build(l,mid);
	a[now].rs = build(mid+1,r);
	return now;
}
void pushup(int now){
	a[now].num = a[a[now].ls].num+a[a[now].rs].num;
}
int update(int now,int w,int cg,int l,int r){
	a[++cnt] = a[now];
	now = cnt;
	if(l == r){
		a[now].num = a[now].num+cg;
		return now;
	}
	int mid;
	mid = (l+r)/2;
	if(w<=mid){
		a[now].ls = update(a[now].ls,w,cg,l,mid);
	}else{
		a[now].rs = update(a[now].rs,w,cg,mid+1,r);
	}
	pushup(now);
	return now;
}
int lowbit(int n){
	return n&-n;
}
void update_tr(int w,int cg){
	int k;
	k = lower_bound(h+1,h+tot+1,b[w])-h;
	for(int i = w;i<=n;i = i+lowbit(i)){
		rt[i] = update(rt[i],k,cg,1,tot);
	}
} 
int find(int k,int l,int r){
	if(l == r){
		return h[l];
	} 
	int num;
	num = 0;
	for(int i = 1;i<=jia[0];i++){
		num = num+a[a[jia[i]].ls].num;
	}
	for(int i = 1;i<=jian[0];i++){
		num = num-a[a[jian[i]].ls].num;
	}
	int mid;
	mid = (l+r)/2;
	if(k<=num){
		for(int i = 1;i<=jia[0];i++){
			jia[i] = a[jia[i]].ls;
		}
		for(int i = 1;i<=jian[0];i++){
			jian[i] = a[jian[i]].ls;
		}
		return find(k,l,mid);
	}else{
		for(int i = 1;i<=jia[0];i++){
			jia[i] = a[jia[i]].rs;
		}
		for(int i = 1;i<=jian[0];i++){
			jian[i] = a[jian[i]].rs;
		}
		return find(k-num,mid+1,r);
	}
}
int find_tr(int l,int r,int k){
	jia[0] = 0;
	jian[0] = 0;
	for(int i = r;i;i = i-lowbit(i)){
		jia[++jia[0]] = rt[i];
	}
	for(int i = l;i;i = i-lowbit(i)){
		jian[++jian[0]] = rt[i];
	}
	return find(k,1,tot);
}
signed main() {
	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;	
	for(int i = 1;i<=n;i++){
		cin>>b[i];
		h[++tot] = b[i];
	}
	for(int i = 1;i<=m;i++){
		cin>>cz[i].op>>cz[i].l>>cz[i].r;
		if(cz[i].op == 'Q'){
			cin>>cz[i].k;
		}else{
			h[++tot] = cz[i].r;
		}
	}
	sort(h+1,h+tot+1);
	tot = unique(h+1,h+tot+1)-h-1;
	rt[0] = build(1,tot);
	for(int i = 1;i<=n;i++){
		int k;
		k = lower_bound(h+1,h+tot+1,b[i])-h;
		rt[i] = update(rt[i-1],k,0,1,tot);
	}
	for(int i = 1;i<=n;i++){
		update_tr(i,1);
	}
	for(int i = 1;i<=m;i++){
		if(cz[i].op == 'C'){
			update_tr(cz[i].l,-1);
			b[cz[i].l] = cz[i].r;
			update_tr(cz[i].l,1);
		}else{
			cout<<find_tr(cz[i].l-1,cz[i].r,cz[i].k)<<"\n";
		}
	}
	return 0;
}