rt，T了5个点，本地跑了几s才出，答案是对的

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;bool f=false;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
#define ll long long
const ll N=60000005,INF=2147483647;
int n,m,a[N];
int root[N],cnt; 
struct node{
	int siz,key,val,rs,ls;
	#define siz(x) T[x].siz
	#define val(x) T[x].val
	#define key(x) T[x].key
	#define ls(x) T[x].ls
	#define rs(x) T[x].rs 
}T[N];
#define update(x) siz(x)=siz(ls(x))+siz(rs(x))+1
inline int newnode(int x){siz(++cnt)=1,key(cnt)=rand(),val(cnt)=x;return cnt;}
void split(int now,int k,int &x,int &y){
	if(!now){x=y=0;return ;}
	if(val(now)<=k) x=now,split(rs(x),k,rs(x),y);
	else y=now,split(ls(y),k,x,ls(y));
	update(now);
	return ;
}
int merge(int x,int y){
	if(!x||!y) return x|y;
	if(key(x)<key(y)){rs(x)=merge(rs(x),y);update(x);return x;}
	else{ls(y)=merge(x,ls(y));update(y);return y;}
}
void insert(int pos,int k){
	int x,y;split(root[pos],k,x,y);
	root[pos]=merge(merge(x,newnode(k)),y);
	return ;
}
void mydelete(int pos,int k){
	int x,y,z;
	split(root[pos],k,x,z),split(x,k-1,x,y);
	y=merge(ls(y),rs(y)),root[pos]=merge(merge(x,y),z);
	return ;
}
int getrank(int pos,int k){
	int x,y,ans;
	split(root[pos],k-1,x,y),ans=siz(x);
	root[pos]=merge(x,y);
	return ans;
}
int getval(int pos,int k){
	int now=root[pos];
	while(1){
		if(siz(ls(now))+1==k) return val(now);
		else if(siz(ls(now))+1>=k) now=ls(now);
		else k-=siz(ls(now))+1,now=rs(now);
	}
	return val(now);
}
int getpre(int pos,int k){
	int x,y,now;split(root[pos],k-1,x,y);now=x;
	while(rs(now)) now=rs(now);
    if(!now) return -INF;
	root[pos]=merge(x,y);
	return val(now);
}
int getnex(int pos,int k){
	int x,y,now;split(root[pos],k,x,y);now=y;
	while(ls(now)) now=ls(now);
    if(!now) return INF;
	root[pos]=merge(x,y);
	return val(now);
}
void build(int x,int l,int r){
    for(register int i=l;i<=r;i++) insert(x,a[i]);
    if(l==r) return ;
    int mid=l+r>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    return ; 
}
int QueryRank(int x,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr) return getrank(x,v);
    int mid=l+r>>1,res=0;
    if(ql<=mid) res=QueryRank(x<<1,l,mid,ql,qr,v);
    if(qr>mid) res+=QueryRank(x<<1|1,mid+1,r,ql,qr,v);
    return res;
}
int QueryVal(int x,int l,int r,int ql,int qr,int v){
    int lc=0,rc=1e9,res=-1;
    while(lc+1<rc){
        int mid=lc+rc>>1;
        if(QueryRank(x,l,r,ql,qr,mid)+1<=v) res=mid,lc=mid;
        else rc=mid;
    }
    return res;
}
void Modify(int x,int l,int r,int v,int c){
    mydelete(x,a[v]);insert(x,c);
    if(l==r){a[v]=c;return ;}
    int mid=l+r>>1;
    if(v<=mid) Modify(x<<1,l,mid,v,c);
    else Modify(x<<1|1,mid+1,r,v,c);
    return ;
}
int QueryPre(int x,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr) return getpre(x,v);
    int mid=l+r>>1,res=-INF;
    if(ql<=mid) res=QueryPre(x<<1,l,mid,ql,qr,v);
    if(qr>mid) res=max(res,QueryPre(x<<1|1,mid+1,r,ql,qr,v));
    return res;
}
int QueryNex(int x,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr) return getnex(x,v);
    int mid=l+r>>1,res=INF;
    if(ql<=mid) res=QueryNex(x<<1,l,mid,ql,qr,v);
    if(qr>mid) res=min(res,QueryNex(x<<1|1,mid+1,r,ql,qr,v));
    return res;
}
char op[2];
int main(){
//	system("fc my.out P2617_11.out");
//	freopen("P2617_11.in","r",stdin);
//	freopen("my.out","w",stdout);
	read(n),read(m);
    for(register int i=1;i<=n;i++) read(a[i]);
    build(1,1,n);
	for(register int i=1,l,r,k;i<=m;++i){
		scanf("%s",op);
        if(op[0]=='Q'){
            read(l),read(r),read(k);
            write(QueryVal(1,1,n,l,r,k)),putchar('\n');
        }
        else{
            read(l),read(k);
            Modify(1,1,n,l,k);
        }
	}
//    system("Pause");
	return 0;
}