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

Sample Output

1

-1

2

2

2

-1

 

用线段树水水就行了，可以记录权值所对应的叶结点，方便判断。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #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\n",querymin(1,1,n)-1); if(t==4) printf("%d\n",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\n",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\n",id[x]-1); } if(t==7) puts(sumv[pos[read()+1]]?"1":"-1"); } return 0;}