记录编号	582502	评测结果	AAAAAAAAAA
题目名称	K小数（简化）	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.300 s
提交时间	2023-09-15 21:08:49	内存使用	4.36 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e5;
//树状数组求第k小数 
int n,m;
int a[N],c[N];
char ch[10];
int lowbit(int x){return x & (-x);}
void add(int x,int z){
    while(x <= 1e5+1){
        c[x] += z;
        x += lowbit(x);
    } 
    return;
}
int ask(int x){
    int ss = 0;
    while(x > 0){
        ss += c[x];
        x -= lowbit(x);
    }
    return ss;
}
int main(){
    freopen("kthnum.in","r",stdin);
    freopen("kthnum.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
       scanf("%d",&a[i]); 
       add(a[i],1);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%s%d",ch,&x);
        if(ch[0] == 'C'){
            scanf("%d",&y);
            add(a[x],-1);
            add(y,1);
            a[x] = y;
        }
        else{
            int l = 1,r = 1e5+1;
            while(l < r){
                int mid = (l + r) >> 1;
                if(ask(mid) >= x)r = mid;
                else l = mid+1;
            }//二分 
            printf("%d\n",l);
        }
    }
    
    return 0; 
}