RT，调了好久只有50pts，过了前面一半

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e5+10,M=2e5+10;

#define lb(x) (x&-x)

int n,m,a[N],b[M],tot;
int rt[N],cnt,tmp1[N],tmp2[N],tot1,tot2;
struct tree{int l,r,sum;}t[M<<6];
struct Query{bool op;int pos,l,r,k;}q[N];

inline void pushup(int p){
    t[p].sum=t[t[p].l].sum+t[t[p].r].sum;
}
int ins(int now,int l,int r,int pos,int k){
    int p=++cnt;t[p]=t[now];
    if(l==r){t[p].sum+=k;return p;}
    int mid=l+r>>1;
    if(pos<=mid)t[p].l=ins(t[now].l,l,mid,pos,k);
    else t[p].r=ins(t[now].r,mid+1,r,pos,k);
    pushup(p);return p;
}
void add(int x,int pos,int k){
    for(;x<=n;x+=lb(x))rt[x]=ins(rt[x],1,tot,pos,k);
}
void init(){
    sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
        add(i,a[i],1);
    }
}
int query(int l,int r,int k){
    if(l==r)return l;
    int mid=l+r>>1,sum=0;
    for(int i=1;i<=tot1;++i)sum+=t[t[tmp1[i]].l].sum;
    for(int i=1;i<=tot2;++i)sum-=t[t[tmp2[i]].l].sum;
    if(k<=sum){
        for(int i=1;i<=tot1;++i)tmp1[i]=t[tmp1[i]].l;
        for(int i=1;i<=tot2;++i)tmp2[i]=t[tmp2[i]].l;
        return query(l,mid,k);
    }else {
        for(int i=1;i<=tot1;++i)tmp1[i]=t[tmp1[i]].r;
        for(int i=1;i<=tot2;++i)tmp2[i]=t[tmp2[i]].r;
        return query(mid+1,r,k-sum);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),b[++tot]=a[i];
    for(int i=1;i<=m;++i){
        char opt;scanf(" %c",&opt);
        q[i].op=opt=='Q';
        if(q[i].op){
            scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        }else{
            scanf("%d%d",&q[i].pos,&q[i].k);
            b[++tot]=q[i].k;
        }
    }
    init();
    for(int i=1;i<=m;++i){
        if(q[i].op){
            tot1=tot2=0;
            for(int j=q[i].r;j;j-=lb(j))tmp1[++tot1]=rt[j];
            for(int j=q[i].l-1;j;j-=lb(j))tmp2[++tot2]=rt[j];
            printf("%d\n",b[query(1,tot,q[i].k)]);
        }else {
            q[i].k=lower_bound(b+1,b+tot+1,q[i].k)-b;
            add(q[i].pos,a[q[i].pos],-1);
            add(q[i].pos,q[i].k,1);
            a[q[i].pos]=q[i].k;
        }
    }
    return 0;
}