离散化去重之后,通过树状数组或线段树维护,查询使用二分,插入删除直接维护,复杂度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]);
}
}
}
}