记录编号	582494	评测结果	WWWWWWWWWW
题目名称	3913.K小数（简化）	最终得分	0
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	0.298 s
提交时间	2023-09-15 20:11:23	内存使用	3.44 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int n,m;
int a[N],v[N];
int c[N];
char ch[10];
void add(int x,int z){
    while(x <= 1e5+1){
        c[x] += z;
        x += x&-x;
    }
    return;
}
int ask(int x){
    int ss = 0;
    while(x > 0){
        ss += c[x];
        x -= x&-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]); 
       a[i]++;
       v[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);y++;
            add(a[x],-1);
            add(y,1);
            v[a[x]]--,v[y]++;
            a[x] = y;
        }
        else{
            int l = 1,r = 1e5+1;
            while(l <= r){
                int mid = (l + r) >> 1;
                int s = ask(mid);
                if(s < x)l = mid+1;
                else if(s > x)r = mid-1;
                else{
                    if(v[mid]){
                        printf("%d\n",mid-1);
                        break;
                    }
                    else{
                        r = mid-1;
                    }
                }
            }
        }
    }
    
    return 0; 
}