rt。代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,q,a[N];
int opt[N][3];
int lsh[2*N],len;

int read()
{
    int res=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
void write(int x)
{
    int st[20],top=0;
    do
    {
        st[++top]=x%10,x/=10;
    }while(x);
    while(top)putchar(st[top--]+'0');
    putchar('\n');
}
namespace seg_in_bit
{
    int tot=0,rt[N];
    struct node
    {
        int sum,lc,rc;
    };
    node val[N<<9];
    #define mid ((l+r)>>1)
    int lb(int x){return x&(-x);}
    void insert(int &x,int l,int r,int pos,int v)
    {
        if(!x)x=++tot;
        val[x].sum+=v;
        if(l==r)
            return;
        if(pos<=mid)insert(val[x].lc,l,mid,pos,v);
        else insert(val[x].rc,mid+1,r,pos,v);
    }
    void update(int x,int y,int v)
    {
        for(;x<=n;x+=lb(x))insert(rt[x],1,len,y,v);
    }
    int tem[N],tmp[N],len1,len2;
    int query(int l,int r,int k)
    {
        if(l==r)return l;
        int res=0;
        for(int i=1;i<=len1;i++)res+=val[val[tem[i]].lc].sum;
        for(int i=1;i<=len2;i++)res-=val[val[tmp[i]].lc].sum;
        if(k<=res)
        {
            for(int i=1;i<=len1;i++)tem[i]=val[tem[i]].lc;
            for(int i=1;i<=len2;i++)tmp[i]=val[tmp[i]].lc;
            return query(l,mid,k);
        }
        else
        {
            for(int i=1;i<=len1;i++)tem[i]=val[tem[i]].rc;
            for(int i=1;i<=len2;i++)tmp[i]=val[tmp[i]].rc;
            return query(mid+1,r,k-res);
        }
    }
    int get_num(int l,int r,int k)
    {
        len1=len2==0;
        l--;
        for(;r;r-=lb(r))tem[++len1]=rt[r];
        for(;l;l-=lb(l))tmp[++len2]=rt[l];
        return query(1,len,k);
    }
};

using namespace seg_in_bit;
int main()
{int t=clock();
    freopen("P2617_11.in","r",stdin);
    freopen("1234.out","w",stdout);
    n=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read(),lsh[++len]=a[i];
    for(int i=1;i<=q;i++)
    {
        char x=getchar();
        while(x!='Q'&&x!='C')x=getchar();
        if(x=='Q')
        {
            opt[i][0]=read();
            opt[i][1]=read();
            opt[i][2]=read();
        }
        else
        {
            opt[i][0]=read();
            opt[i][1]=read();
            lsh[++len]=opt[i][1];
        }
    }
    sort(lsh+1,lsh+len+1);
    len=unique(lsh+1,lsh+len+1)-lsh-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
        update(i,a[i],1);
    }
    for(int i=1;i<=q;i++)
    {
        if(opt[i][2])write(lsh[get_num(opt[i][0],opt[i][1],opt[i][2])]);
        else
        {
            opt[i][1]=lower_bound(lsh+1,lsh+len+1,opt[i][1])-lsh;
            update(opt[i][0],a[opt[i][0]],-1);
            update(opt[i][0],opt[i][1],1);
            a[opt[i][0]]=opt[i][1];
        }
    }
    return 0;
}