Description
设计数据结构支持:
1 x 若x不存在,插入x
2 x 若x存在,删除x
3 输出当前最小值,若不存在输出-1
4 输出当前最大值,若不存在输出-1
5 x 输出x的前驱,若不存在输出-1
6 x 输出x的后继,若不存在输出-1
7 x 若x存在,输出1,否则输出-1
Input
第一行给出n,m 表示出现数的范围和操作个数
接下来m行给出操作
n<=10^6,m<=2*10^6,0<=x<n
Output
Sample Input
10 11
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2
Sample Output
1
-1
2
2
2
-1
-1
2
2
2
-1
用线段树水水就行了，可以记录权值所对应的叶结点，方便判断。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; const int BufferSize=1<<16; char buffer[BufferSize],*head,*tail; inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++; } inline int read() { int x=0,f=1;char c=Getchar(); for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1000010; int sumv[maxn*3],pos[maxn],id[maxn*3]; void build(int o,int l,int r) { if(l==r) pos[l]=o,id[o]=l; else { int mid=l+r>>1,lc=o<<1,rc=lc|1; build(lc,l,mid);build(rc,mid+1,r); } } int querymin(int o,int l,int r) { if(!sumv[o]) return 0; if(l==r) return l; int mid=l+r>>1,lc=o<<1,rc=lc|1; if(sumv[lc]) return querymin(lc,l,mid); return querymin(rc,mid+1,r); } int querymax(int o,int l,int r) { if(!sumv[o]) return 0; if(l==r) return l; int mid=l+r>>1,lc=o<<1,rc=lc|1; if(sumv[rc]) return querymax(rc,mid+1,r); return querymax(lc,l,mid); } int main() { int n=read()+1,m=read(); build(1,1,n); while(m--) { int t=read(),x; if(t==1||t==2) { x=pos[read()+1]; if((sumv[x]&&t==2)||(!sumv[x]&&t==1)) { while(x) { sumv[x]+=(t==2?-1:1); x>>=1; } } } if(t==3) printf("%d ",querymin(1,1,n)-1); if(t==4) printf("%d ",querymax(1,1,n)-1); if(t==5) { int x=pos[read()+1]; while(x!=1) { int fa=x>>1; if(fa&&x!=fa<<1&&sumv[fa<<1]) {x=fa<<1;break;} x>>=1; } if(x==1) {puts("-1");continue;} while(!id[x]) { if(sumv[(x<<1)|1]) x=(x<<1)|1; else x<<=1; } printf("%d ",id[x]-1); } if(t==6) { int x=pos[read()+1]; while(x!=1) { int fa=x>>1; if(fa&&x==fa<<1&&sumv[(fa<<1)|1]) {x=(fa<<1)|1;break;} x>>=1; } if(x==1) {puts("-1");continue;} while(!id[x]) { if(sumv[x<<1]) x<<=1; else x=(x<<1)|1; } printf("%d ",id[x]-1); } if(t==7) puts(sumv[pos[read()+1]]?"1":"-1"); } return 0; }