rt，TLE 50pts，本人真的很不会卡常。开了光读之后好像寄了只过了最后一个点其它全部 T，然后样例输入也有问题，求教/kk。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<21],*p1=buf,*p2=buf;
const int N=1e5+113,V=2e5+113,sq=500;
int n,m,a[N],cnt_que,cnt_upd,ans[N],idx;
int id[V],bl[sq],br[sq],len,vmax,b[V],sum[sq],cnt[V];
int L,R,T;
il int read(){
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct query{
    int l,r,x,t,id;
}q[N];
il bool cmp(query x,query y){
    if(id[x.l]^id[y.l])return x.l<y.l;
    if(id[x.r]^id[y.r])return x.r<y.r;
    return x.t<y.t;
}
struct update{
    int place,x;
}u[N];
il void init(){
    for(re int i=1;i<=cnt_upd;i++)b[++idx]=u[i].x;
    vmax=idx;
    sort(b+1,b+1+vmax);
    vmax=unique(b+1,b+1+vmax)-b-1;
    len=sqrt(vmax);
    for(re int i=1;i<=vmax;i++)id[i]=(i-1)/len+1;
    for(re int i=1;i<=id[vmax];i++)
        bl[i]=br[i-1]+1,br[i]=i*len;
    br[id[vmax]]=vmax;
    for(re int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+vmax,a[i])-b;
    for(re int i=1;i<=cnt_upd;i++)
        u[i].x=lower_bound(b+1,b+1+vmax,u[i].x)-b;
}
#define Add(x) cnt[x]++,sum[id[x]]++
#define Del(x) cnt[x]--,sum[id[x]]--
il int solve(int x){
    re int tot=0;
    for(re int i=1;i<=id[vmax];i++){
        tot+=sum[i];
        if(tot>=x){
            tot-=sum[i];
            for(re int j=bl[i];j<=br[i];j++){
                tot+=cnt[j];
                if(tot>=x)return b[j];
            }
        }
    }
}
int main(){
    n=read(),m=read();
    len=sqrt(n);
    for(re int i=1;i<=n;i++)
        a[i]=read(),id[i]=(i-1)/len+1,b[++idx]=a[i];
    for(re int i=1;i<=m;i++){
        char op[5];
        scanf("%s",op);
        if(op[0]=='C'){
            cnt_upd++;
            u[cnt_upd].place=read(),u[cnt_upd].x=read();
            continue;
        }
        cnt_que++;
        q[cnt_que].l=read(),q[cnt_que].r=read(),q[cnt_que].x=read();
        q[cnt_que].t=cnt_upd,q[cnt_que].id=cnt_que;
    }
    sort(q+1,q+1+cnt_que,cmp);
    init();
    L=1;
    for(re int i=1;i<=cnt_que;i++){
        re int l=q[i].l,r=q[i].r,x=q[i].x;
        while(R<r)R++,Add(a[R]);
        while(L>l)L--,Add(a[L]);
        while(R>r)Del(a[R]),R--;
        while(L<l)Del(a[L]),L++;
        while(T<q[i].t){
            T++;
            int pla=u[T].place;
            if(pla>=l&&pla<=r)Del(a[pla]),Add(u[T].x);
            swap(u[T].x,a[pla]);
        }
        while(T>q[i].t){
            int pla=u[T].place;
            if(pla>=l&&pla<=r)Del(a[pla]),Add(u[T].x);
            swap(u[T].x,a[pla]);
            T--;
        }
        ans[q[i].id]=solve(x);
    }
    for(re int i=1;i<=cnt_que;i++)cout<<ans[i]<<'\n';
    return 0;
}