只过了样例

#include <bits/stdc++.h>
using namespace std;
int n,m,idx,a[200010],b[200010],rk[200010],len,rt[200010],cnt;
struct node{
    int l,r,k,x,y;
}q[100010];
int read(){
    int ans=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') {
        ans=ans*10+(c-'0');
        c=getchar();
    }
    return ans;
}
struct p{
    int l,r,val;
}tr[30000000];
int lowbit(int x) {
    return x&(-x);
}
void pushup(int x) {
    tr[x].val=tr[tr[x].l].val+tr[tr[x].r].val;
}
void modify(int &now,int l,int r,int target,int val){
    if(!now) now=++cnt;
    if(l==r) {
        tr[now].val+=val;
        return;
    }
    int mid=(l+r)/2;
    if(target<=mid) modify(tr[now].l,l,mid,target,val);
    else modify(tr[now].r,mid+1,r,target,val);
    pushup(now);
}
void add(int pl,int w,int x) {
    for(;pl<=n;pl+=lowbit(pl)) {
        modify(rt[pl],1,n,w,x);
    }
}
void build() {
    for(int i=1;i<=n;i++) {
        add(i,rk[i],1);
    }
}
int query(int k,int targetl,int targetr) {
    int lnode[100010]={0},rnode[100010]={0},totl=0,totr=0;
    for(int i=targetl-1;i;i-=lowbit(i)) {
        lnode[++totl]=rt[i];
    }
    for(int i=targetr;i;i-=lowbit(i)) {
        rnode[++totr]=rt[i];
    }
    int nowl=1,nowr=n;
    while(nowl<nowr) {
        int mid=(nowl+nowr)/2,sum=0;
        if(targetl!=1) {
            for(int i=1;i<=totl;i++) {
                sum-=tr[tr[lnode[i]].l].val;
            }
        }
        for(int i=1;i<=totr;i++) {
            sum+=tr[tr[rnode[i]].l].val;
        }
        if(k<=sum) {
            if(targetl!=1) {
                for(int i=1;i<=totl;i++) {
                    lnode[i]=tr[lnode[i]].l;
                }
            }
            for(int i=1;i<=totr;i++) {
                rnode[i]=tr[rnode[i]].l;
            }
            nowr=mid;
        }
        else {
            k-=sum;
            if(targetl!=1) {
                for(int i=1;i<=totl;i++) {
                    lnode[i]=tr[lnode[i]].r;
                }
            }
            for(int i=1;i<=totr;i++) {
                rnode[i]=tr[rnode[i]].r;
            }
            nowl=mid+1;
        }
    }
    return nowl;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) {
        cin>>a[++idx];
        b[idx]=a[idx];
    }
    for(int i=1;i<=m;i++) {
        char c;
        cin>>c;
        if(c=='Q') {
            cin>>q[i].l>>q[i].r>>q[i].k;
        }
        else {
            cin>>q[i].x>>q[i].y;
            a[++idx]=q[i].y;
            b[idx]=a[idx];
        }
    }
    sort(b+1,b+idx+1);
    len=unique(b+1,b+idx+1)-b-1;
    for(int i=1;i<=idx;i++) {
        rk[i]=lower_bound(b+1,b+len+1,a[i])-b;
    }
    len=idx;
    idx++;
    build();
    for(int i=1;i<=m;i++) {
        if(q[i].l==0) {
            add(q[i].x,rk[q[i].x],-1);
            b[q[i].x]=q[i].y;
            rk[q[i].x]=lower_bound(b+1,b+len+1,q[i].y)-b;
            add(q[i].x,rk[q[i].x],1);
        }
        else {
            cout<<b[query(q[i].k,q[i].l,q[i].r)]<<'\n';
        }
    }
    return 0;
}