rt，#12 WA，估计是二分的锅

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int maxn = 1e5+5;
const double alpha = 0.7;
int n,m,a[maxn],l,r,k;
char op;
namespace Scapegoat{
    struct node{
        int num,v,l,r,sz,cnt;
    }t[maxn*128];
    int tot,tmp[maxn];
    void pushup(int u){
        t[u].sz=t[t[u].l].sz+t[t[u].r].sz+t[u].v;
        t[u].cnt=t[t[u].l].cnt+t[t[u].r].cnt+1;
    }
    bool can_rebuild(int u){
        return t[u].v&&max(t[t[u].l].cnt,t[t[u].r].cnt)>alpha*t[u].cnt;
    }
    void flatten(int u,int &c){
        if(!u)return;
        flatten(t[u].l,c);
        if(t[u].v)tmp[c++]=u;
        flatten(t[u].r,c);
    }
    int build(int l,int r){
        if(l>=r)return 0;
        int mid=(l+r)>>1;
        t[tmp[mid]].l=build(l,mid);
        t[tmp[mid]].r=build(mid+1,r);
        pushup(tmp[mid]);
        return tmp[mid];
    }
    void rebuild(int &u){
        int c=0;
        flatten(u,c);
        u=build(0,c);
    }
    void insert(int &u,int num){
        if(!u){
            u=++tot;
            t[u].num=num;
            t[u].v=1;
        }
        else if(t[u].num<num)insert(t[u].r,num);
        else insert(t[u].l,num);
        pushup(u);
        if(can_rebuild(u))rebuild(u);
    }
    void remove(int u,int num){
        if(!u)return;
        if(t[u].num==num)--t[u].v;
        else if(t[u].num<num)remove(t[u].r,num);
        else remove(t[u].l,num);
        pushup(u);
    }
    int rank(int u,int num){
        if(!u)return 0;
        if(t[u].num==num)return t[t[u].l].sz;
        else if(t[u].num<num)return rank(t[u].r,num)+t[t[u].l].sz+t[u].v;
        else return rank(t[u].l,num);
    }
    int findkth(int u,int k){
        if(k<=t[t[u].l].sz)return findkth(t[u].l,k);
        else if(k<=t[t[u].l].sz+t[u].v)return t[u].num;
        else return findkth(t[u].r,k-t[t[u].l].sz-t[u].v);
    }
}
namespace Segment{
    int rt[maxn*4];
    bool in_range(int L,int R,int l,int r){
        return (l<=L)&&(R<=r);
    }
    bool out_range(int L,int R,int l,int r){
        return (r<L)||(R<l);
    }
    void build(int u,int L,int R){
        for(int i=L;i<=R;++i)Scapegoat::insert(rt[u],a[i]);
        if(L==R)return;
        int M=(L+R)>>1;
        build(u*2,L,M);
        build(u*2+1,M+1,R);
    }
    void modify(int u,int L,int R,int x,int k){
        Scapegoat::remove(rt[u],a[x]);
        Scapegoat::insert(rt[u],k);
        if(L==R)return;
        int M=(L+R)>>1;
        if(x<=M)modify(u*2,L,M,x,k);
        else modify(u*2+1,M+1,R,x,k);
    }
    int rank(int u,int L,int R,int l,int r,int x){
        if(in_range(L,R,l,r))return Scapegoat::rank(rt[u],x);
        if(out_range(L,R,l,r))return 0;
        int M=(L+R)>>1;
        return rank(u*2,L,M,l,r,x)+rank(u*2+1,M+1,R,l,r,x);
    }
    int findkth(int L,int R,int k){
        int l=-5,r=1e9+5;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(rank(1,1,n,L,R,mid)<k)l=mid;
            else r=mid-1;
        }
        return r;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    Segment::build(1,1,n);
    while(m--){
        cin>>op;
        if(op=='Q'){
            cin>>l>>r>>k;
            cout<<Segment::findkth(l,r,k)<<'\n';
        }
        if(op=='C'){
            cin>>l>>r;
            Segment::modify(1,1,n,l,r);
            a[l]=r;
        }
    }
    return 0;
}

record