题解 | #wyh的天鹅（树状数组）#

离散化去重之后，通过树状数组或线段树维护，查询使用二分，插入删除直接维护，复杂度nlogn

#include<bits/stdc++.h>
using namespace std;
inline int lowbit(int x){return x&-x;}
const int N = 5e5+10;
vector<int>alls;
int tr[N<<2],n,m,T,a[N];
char cz[8];
struct op{
    char p[8];
    int x;
}s[N];
inline void modify(int x,int v){
    for(;x<=n;x+=lowbit(x)){
        tr[x]+=v;
    }
}
inline int query(int x){
    int res=0;
    for(;x;x-=lowbit(x))res+=tr[x];
    return res;
}
int main(){
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        alls.resize(n+1+m);
        memset(tr,false,sizeof tr);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            alls[i+1]=a[i];
        }
        for(int i=0;i<m;i++)
        {
            scanf("%s %d",s[i].p,&s[i].x);
            alls[i+1+n]=s[i].x;
        }
        sort(alls.begin()+1,alls.end());
        alls.erase(unique(alls.begin()+1,alls.end()),alls.end());
        n=alls.size();
        for(int i=0;i<n;i++){
           modify(lower_bound(alls.begin()+1,alls.end(),a[i])-alls.begin(),1);
        }
        int res=n;
        for(int i=0;i<m;i++)
        {
            int x=s[i].x;
            if(!strcmp("insert",s[i].p)){res++;
                modify(lower_bound(alls.begin()+1,alls.end(),x)-alls.begin(),1);
            }   
            else if(!strcmp("delete",s[i].p)){res--;
                modify(lower_bound(alls.begin()+1,alls.end(),x)-alls.begin(),-1);
            }
            else {
                int l=1,r=n;
                x=res-x+1;
                while(l<r){
                    int mid=l+r>>1;
                    if(query(mid)>=x)r=mid;
                    else l=mid+1;
                }
                printf("%d\n",alls[l]);
            }
        }
    }
}