思路:树状数组+二分搜索,具体见代码吧。
#include#include #include #include /*AC树状数组+二分搜索题意:给出三种操作 0 e:将e放入容器中 1 e:将e从容器中删除,若不存在,则输出No Elment! 2 a k:搜索容器中比a大的第k个数,若不存在,则输出Not Find!思路:树状数组+二分搜索,具体见代码吧。*/using namespace std;const int maxn=100005;int m;int c[maxn]; //树状数组int vis[maxn]; //vis[i]表示元素i的个数int lowbit(int x){ return x&(-x);}void update(int i,int v){ while(i 1){ mid=(l+r)>>1; tmp=sum(mid); if(k<=tmp) r=mid; else l=mid; } return r;}int main(){ int op,e,k; int n; //目前存放的元素个数 while(scanf("%d",&m)!=EOF){ memset(vis,0,sizeof(vis)); memset(c,0,sizeof(c)); n=0; for(int i=1;i<=m;i++){ scanf("%d",&op); if(op==0){ scanf("%d",&e); vis[e]++; update(e,1); n++; } else if(op==1){ scanf("%d",&e); if(!vis[e]) printf("No Elment!\n"); else{ vis[e]--; update(e,-1); n--; } } else{ scanf("%d%d",&e,&k); int t=sum(e); // 目前<=e的元素有t个,转化成搜索第t+k个大的元素 //若t+k直接大于n,则不存在该元素 if(t+k>n) printf("Not Find!\n"); else{ k=k+t; printf("%d\n",binarySearch(k)); } } } } return 0;}