bzoj 3685: 普通van Emde Boas树

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

By Zky

题解：

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

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

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

提一下前驱的找法：

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

后继的话找法差不多。。

#include<stdio.h>

#include<iostream>

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;

}

巴特西