3685: 普通van Emde Boas树

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

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

Source

题解：

vEB树是什么东东???。。。。

按照题目描述用线段树做就好了。。。。

按0~n划分区间，记录区间中存在的数的个数。

提一下前驱的找法：

对于x，在整个区间内找x-1，每次递归的两次区间，如果x-1在左区间，那么直接递归左区间，如果在右区间，判断右区间有无答案，没有的话则当前答案是左区间内的最大值。

后继的话找法差不多。。

#include
      
       #include
       
        using namespace std;const int N=1000005;#define p1 (p<<1)#define p2 (p<<1|1)int n,m,i,p,x,t[N<<2];inline void read(int &v){    char ch,fu=0;    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());    if(ch=='-') fu=1, ch=getchar();    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';    if(fu) v=-v;}void update(int l,int r,int x,int y,int p){	if(l==r)	{		t[p]=y;		return;	}	int mid=(l+r)>>1;	if(x<=mid) update(l,mid,x,y,p1);else update(mid+1,r,x,y,p2);	t[p]=t[p1]+t[p2];}int Min(int l,int r,int p){	if(!t[p]) return -1;	if(l==r) return l;	int mid=(l+r)>>1;	if(t[p1]) return Min(l,mid,p1);else return Min(mid+1,r,p2);}int Max(int l,int r,int p){	if(!t[p]) return -1;	if(l==r) return l;	int mid=(l+r)>>1;	if(t[p2]) return Max(mid+1,r,p2);else return Max(l,mid,p1);}int find(int l,int r,int x,int p){	if(!t[p]) return -1;	if(l==r) return 1;	int mid=(l+r)>>1;	if(x<=mid) return find(l,mid,x,p1);else return find(mid+1,r,x,p2);}int pre(int l,int r,int x,int p){	if(x<0) return -1;	if(!t[p]) return -1;	if(l==r) return l;	int mid=(l+r)>>1;	if(x<=mid) return pre(l,mid,x,p1);else	{		int tmp=pre(mid+1,r,x,p2);		if(tmp==-1) return Max(l,mid,p1);else return tmp;	}}int last(int l,int r,int x,int p){	if(x>n) return -1;	if(!t[p]) return -1;	if(l==r) return l;	int mid=(l+r)>>1;	if(x>mid) return last(mid+1,r,x,p2);else	{		int tmp=last(l,mid,x,p1);		if(tmp==-1) return Min(mid+1,r,p2);else return tmp;	}}int main(){	read(n),read(m);	for(i=1;i<=m;i++)	{		read(p);		if(p==1)		{			read(x);			update(0,n,x,1,1);		} else		if(p==2)		{			read(x);			update(0,n,x,0,1);		} else		if(p==3) printf("%d\n",Min(0,n,1));else		if(p==4) printf("%d\n",Max(0,n,1));else		if(p==7) 		{			read(x);			printf("%d\n",find(0,n,x,1));		} else		if(p==5)		{			read(x);			printf("%d\n",pre(0,n,x-1,1));		} else		{			read(x);			printf("%d\n",last(0,n,x+1,1));		}	}	return 0;}