输入求调（玄关）

#include <bits/stdc++.h>
#define itn long long 
using namespace std;
static const int N=1000000;
int n,m;
int a[N],b[N];
int vn;
struct Operate{int typ,x,y,kth;}OP[N];
int blngl[N];
int blngv[N];
int L[N],R[N];
int Cntv,Cntl;
int lLngth,vLngth;
int vlcnt[320][N];
int cvlcnt[320][450];

inline void modify(int x,int y){
    for(int i=blngl[x];i<=Cntl;i++){
        vlcnt[i][a[x]]--;
        cvlcnt[i][blngv[a[x]]]--;
        vlcnt[i][y]++;
        cvlcnt[i][blngv[y]]++;
    }
    a[x]=y;
}
inline void Collect(int l,int r,int kth){
    int vl,vr,tmp=0;
    unordered_map<int,int> pcvcnt,pvcnt;
    if(blngl[l]==blngl[r]){
        for(int i=l;i<=r;i++){
            pvcnt[a[i]]++;
            pcvcnt[blngv[a[i]]]++;
        }
        for(int i=1;i<=Cntv;i++){ 
            tmp+=pcvcnt[i];
            if(tmp>=kth){
                tmp-=pcvcnt[i];
                vl=(i-1)*vLngth+1;
                vr=i*vLngth;
                break;
            }
        }
        for(int i=vl;i<=vr;i++){
            tmp+=pvcnt[i];
            if(tmp>=kth){
                cout<<b[i]<<'\n';
                return ;
            }
        }
    }
    else{
        for(int i=l;i<=R[blngl[l]];l++){
            pvcnt[a[i]]++;
            pcvcnt[blngv[a[i]]]++;
        }
        for(int i=L[blngl[r]];i<=r;l++){
            pvcnt[a[i]]++;
            pcvcnt[blngv[a[i]]]++;
        }
        for(int i=1;i<=Cntv;i++){
            tmp+=pcvcnt[i]+cvlcnt[blngl[r]-1][i]-cvlcnt[blngl[l]][i];
            if(tmp>=kth){
                tmp-=pcvcnt[i]+cvlcnt[blngl[r]-1][i]-cvlcnt[blngl[l]][i];
                vl=(i-1)*vLngth+1;
                vr=i*vLngth;
                break;
            }
        }
        for(int i=vl;i<=vr;i++){
            tmp+=pvcnt[i]+vlcnt[blngl[r]-1][i]-vlcnt[blngl[l]][i];
            if(tmp>=kth){
                cout<<b[i]<<'\n';
                return ;
            }   
        }
    }
}

signed main(){
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[++vn]=a[i];
    }
    for(int i=1;i<=m;i++){
        char op;
        int x,y,k;
        cin>>op;
        if(op=='Q'){
            cin>>x>>y>>k;
            OP[i]={1,x,y,k};
        }
        else{
            cin>>x>>y;
            OP[i]={2,x,y,-1};
            b[++vn]=y;
        }
    }//就是这个循环就死了，为啥呢？？？
    sort(b+1,b+1+vn);
    vn=unique(b+1,b+1+vn)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+vn,a[i])-b;

    lLngth=sqrt(n);
    vLngth=sqrt(vn);
    for(int i=1;i<=n;i++)
        blngl[i]=(i-1)/lLngth+1;
    for(int i=1;i<=vn;i++)
        blngv[i]=(i-1)/vLngth+1;
    Cntl=blngl[n];
    Cntv=blngv[vn];
    for(int i=1;i<=Cntl;i++){
        L[i]=R[i-1]+1;
        R[i]=min(L[i]+lLngth-1,n);
        for(int j=1;j<=vn;j++)
            vlcnt[i][j]=vlcnt[i-1][j];
        for(int j=1;j<=Cntv;j++)
            cvlcnt[i][j]=cvlcnt[i-1][j];
        for(int j=L[i];j<=R[i];j++){
            ++vlcnt[i][a[j]];
            ++cvlcnt[i][blngv[a[j]]];
        }
    }
    for(int i=1;i<=m;i++){
        if(OP[i].typ==1)
            Collect(OP[i].x,OP[i].y,OP[i].kth);
        else
            modify(OP[i].x,lower_bound(b+1,b+1+vn,OP[i].y)-b);
    }
    return 0;
}