原题链接

权值线段树

空间同插入数的数量有关系

int t,n,m,k,idx;
struct code{
    int l,r;
    int val;
}tr[N*40];

int c[N],v[N],s[M];
int rc[N];
LL vc[N];

void update(int p){
    tr[p].val=tr[tr[p].l].val+tr[tr[p].r].val;
}
// 在权值的基础上建立线段树即可
// 可以依据权值来查询在区间的信息
void change(int&p,int l,int r,int pos,int val){
    if(!p) p=++idx;
    if(l==r){
        tr[p].val+=val;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) change(tr[p].l,l,mid,pos,val);
    else change(tr[p].r,mid+1,r,pos,val);
    update(p);
    return ;
}
int query(int p,int l,int r,int L,int R){
    if(!p) return 0;
    if(L<=l and r<=R) return tr[p].val;
    int mid=l+r>>1;
    int res = 0;
    if(L<=mid) res+=query(tr[p].l,l,mid,L,R);
    if(R>mid)  res+=query(tr[p].r,mid+1,r,L,R);
    return res;
}
void clear(){
    for(int i=1;i<=n;i++) rc[i]=vc[i]=0;
    for(int i=1;i<=idx;i++) tr[i].l=tr[i].r=tr[i].val=0;
    idx=0;
}

模板题
树套树维护带修改的区间第k大,在每一个位置(点上面)的基础上建立一棵权值线段树然后使用树状数组来维护区间信息

int t,n,m,vn;
struct code{
    int op;
    int l,r,x;
}Q[N];
int a[N];
struct tree{
    int l,r,v;
}tr[310*N];
int rt[N],idx;

void change(int&p,int l,int r,int pos,int val){
    if(!p) p = ++ idx;
    tr[p].v += val;
    if(l==r) return ;
    int mid = l+r>>1;
    if(pos<=mid) change(tr[p].l,l,mid,pos,val);
    else change(tr[p].r,mid+1,r,pos,val);
}
// 一个数影响的区间
void add(int pos,int x,int val){
    while(pos<=n){
        change(rt[pos],1,vn,x,val);
        pos += lowbit(pos);
    }
}

int n1,n2;
int t1[N],t2[N];

int kth(int l,int r,int k){
    if(l==r) return l;

    int mid = l+r>>1;

    int sum = 0;

    for(int i=1;i<=n2;i++)
        sum += tr[tr[t2[i]].l].v;

    for(int i=1;i<=n1;i++)
        sum -= tr[tr[t1[i]].l].v;

    if(sum>=k){
        for(int i=1;i<=n1;i++)
            t1[i] = tr[t1[i]].l;

        for(int i=1;i<=n2;i++)
            t2[i] = tr[t2[i]].l;

        return kth(l,mid,k);
    }
    else{
        for(int i=1;i<=n1;i++)
            t1[i] = tr[t1[i]].r;

        for(int i=1;i<=n2;i++)
            t2[i] = tr[t2[i]].r;

        return kth(mid+1,r,k-sum);
    }
}
int anskth(int l,int r,int k){

    n1 = n2 = 0;
    for(int i=l-1;i>=1;i-=lowbit(i))
        t1[++n1] = rt[i];
    for(int i=r;i>=1;i-=lowbit(i))
        t2[++n2] = rt[i];   
    return kth(1,vn,k);
}
void solve(){

    vector<int> v;

    cin >> n >> m;

    for(int i=1;i<=n;i++){
        cin >> a[i];
        v.push_back(a[i]);      
    }

    for(int i=1;i<=m;i++){
        char op; int l,r,k,pos,x;
        cin >> op;
        if(op == 'Q'){
            cin >> l >> r >> k;
            e[i] = {1,l,r,k};
        }
        else{
            cin >> pos >> x;
            e[i] = {2,pos,x};
            v.push_back(x);
        }
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    auto find = [&](int x){
        return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
    };

    vn = v.size();

    for(int i=1;i<=n;i++) add(i,find(a[i]),1);

    for(int i=1;i<=m;i++){
        auto [op,l,r,k] = e[i];
        if(op == 1){
            cout << v[ansthk(l,r,k)-1] << endl;
        }
        else{
            add(l,find(a[l]),-1);
            a[l] = r;
            add(l,find(a[l]),1);
        }
    }

    return ;
}