和不带修的没啥区别，就把数换一换就好了。

#include<cstdio>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=7e4+5;
const int inf=1e9+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
} 
struct node{int op,x,y,z;}q[N],lq[N],rq[N];
int ans[N],c[N],n,a[N];
inline void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
/*
若修改操作在查询操作前，那么入队时，修改操作在查询操作前
若查询操作在修改操作前，则没有影响 
*/
void solve(int l,int r,int st,int ed)
{
    if(l==r){for(int i=st;i<=ed;i++)if(q[i].op>0)ans[q[i].op]=l;return ;}
    int mid=l+r>>1,ls=0,rs=0;
    for(int i=st;i<=ed;i++)
    {
        if(q[i].op<=0)
        {
            if(q[i].y<=mid)add(q[i].x,q[i].z),lq[++ls]=q[i];
            else rq[++rs]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);
            if(cnt>=q[i].z)lq[++ls]=q[i];
            else q[i].z-=cnt,rq[++rs]=q[i];
        }
    }
    for(int i=1;i<=ls;i++)if(lq[i].op<=0)add(lq[i].x,-lq[i].z);
    for(int i=1;i<=ls;i++)q[st+i-1]=lq[i];
    for(int i=1;i<=rs;i++)q[st+i+ls-1]=rq[i];//按值域排 
    if(ls)solve(l,mid,st,st+ls-1);
    if(rs)solve(mid+1,r,st+ls,ed);
}
int main()
{
    int T;qr(T);
    while(T--)
    {
        int m;qr(n),qr(m);
        for(int i=1;i<=n;i++)
        {
            q[i].op=0,q[i].z=1,q[i].x=i;qr(q[i].y);
            a[i]=q[i].y;
        }
        int t=0,sz=n;
        for(int i=n+1;i<=n+m;i++)
        {
            char op[3];scanf("%s",op);
            if(op[0]=='Q')q[++sz].op=++t,qr(q[sz].x),qr(q[sz].y),qr(q[sz].z);
            else
            {
                q[++sz].op=-1,qr(q[sz].x),q[sz].y=a[q[sz].x],q[sz].z=-1;
                q[++sz].op=0,qr(q[sz].y),q[sz].x=q[sz-1].x,q[sz].z=1;
                a[q[sz].x]=q[sz].y;
            }
        }
        solve(-inf,inf,1,sz);
        for(int i=1;i<=t;i++)qw(ans[i]),puts("");
    }
    return 0;
}

主席树做法:
开个树状数组记录增减信息就好了。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=6e4+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int op,l,r,k;}q[N];
int a[N],arr[N],n,len,b[N];
void disc()
{
    sort(arr+1,arr+len+1);int sz=0;
    for(int i=1;i<=len;i++)
        if(i==1||arr[i]!=arr[i-1])arr[++sz]=arr[i];
    len=sz;
}
inline int get(int d)
{
    int l=1,r=len;
    while(l<r)
    {
        int mid=l+r>>1;
        if(arr[mid]<d)l=mid+1;
        else r=mid;
    }
    return l;
}
struct HJTSeg{int l,r,sum;}t[N*50];int cnt,root[N];
int c[N],c1[N],c2[N],l1,l2;
void update(int l,int r,int &x,int y,int pos)
{
    t[x=++cnt]=t[y];++t[x].sum;
    if(l==r)return ;
    int mid=l+r>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
    else update(mid+1,r,t[x].r,t[y].r,pos);
}
void change(int l,int r,int &x,int pos,int ad)
{
    if(!x)x=++cnt,t[x]=(HJTSeg){0,0,0};
    t[x].sum+=ad;
    if(l==r)return ;
    int mid=l+r>>1;
    if(pos<=mid)change(l,mid,t[x].l,pos,ad);
    else change(mid+1,r,t[x].r,pos,ad);
}
void change(int k,int val)
{
    int x=a[k],y=get(val);a[k]=y;
    for(;k<=n;k+=k&-k)change(1,len,c[k],x,-1),change(1,len,c[k],y,1);
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r)return l;
    int mid=l+r>>1,sum=t[t[x].l].sum-t[t[y].l].sum;
    for(int i=1;i<=l1;i++)sum+=t[t[c1[i]].l].sum;
    for(int i=1;i<=l2;i++)sum-=t[t[c2[i]].l].sum;
    if(sum>=k)
    {
        for(int i=1;i<=l1;i++)c1[i]=t[c1[i]].l;
        for(int i=1;i<=l2;i++)c2[i]=t[c2[i]].l;
        return query(l,mid,t[x].l,t[y].l,k);
    }
    else
    {
        for(int i=1;i<=l1;i++)c1[i]=t[c1[i]].r;
        for(int i=1;i<=l2;i++)c2[i]=t[c2[i]].r;
        return query(mid+1,r,t[x].r,t[y].r,k-sum);
    }
}
void query(int l,int r,int k)
{
    l1=l2=0;
    for(int i=r;i;i-=i&-i)if(c[i])c1[++l1]=c[i];
    for(int i=l-1;i;i-=i&-i)if(c[i])c2[++l2]=c[i];
    int ans=query(1,len,root[r],root[l-1],k);
    qw(arr[ans]);puts("");
}
int main()
{
    //freopen("a.in","r",stdin);
    int T;qr(T);
    while(T--)
    {
        qr(n);int m;qr(m);memset(c,0,sizeof(c));
        root[0]=0;
        for(int i=1;i<=n;i++)qr(a[i]),arr[i]=a[i];
        len=n;cnt=0;
        for(int i=1;i<=m;i++)
        {
            char op[3];scanf("%s",op);
            if(op[0]=='Q')q[i].op=1,qr(q[i].l),qr(q[i].r),qr(q[i].k);
            else q[i].op=2,qr(q[i].l),qr(q[i].r),arr[++len]=q[i].r;
        }
        if(T==0)
            T--,++T;
        disc();
        for(int i=1;i<=n;i++)
        {
            a[i]=get(a[i]);
            update(1,len,root[i],root[i-1],a[i]);
        }
        for(int i=1;i<=m;i++)
        {
            if(q[i].op==1)query(q[i].l,q[i].r,q[i].k);
            else change(q[i].l,q[i].r);
        }
    }
    return 0;
}