【bzoj3685】普通van Emde Boas树权值zkw线段树

原文地址：http://www.cnblogs.com/GXZlegend/p/6809743.html

题目描述

设计数据结构支持:
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

输入

第一行给出n,m 表示出现数的范围和操作个数
接下来m行给出操作
n<=10^6,m<=2*10^6,0<=x<n

样例输入

10 11
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2

样例输出

1
-1
2
2
2
-1

题解

权值zkw线段树，无耻地卡了卡Treap

首先全是Treap的基础操作

然后是正常权值线段树代码大概50行左右

非要搞一个权值zkw线段树。。。

第一次写还写得很丑。。。

不过常数上还是非常可观。

1、2、7是权值线段树基础操作，3、4可以通过贪心轻松搞定。

5、6需要先找到前驱后继的范围再进行查询。

代码太长了。。。凑合看吧。。。

#include <cstdio>

int si[4000010] , k = 1;

void update(int p , int a)

{

	si[k + p] = a;

	int i;

	for(i = (k + p) >> 1 ; i ; i >>= 1) si[i] = si[i << 1] + si[i << 1 | 1];

}

int querymin()

{

	if(!si[1]) return -1;

	int i = 1;

	while(i <= k)

	{

		if(si[i << 1]) i = i << 1;

		else i = i << 1 | 1;

	}

	return i - k - 1;

}

int querymax()

{

	if(!si[1]) return -1;

	int i = 1;

	while(i <= k)

	{

		if(si[i << 1 | 1]) i = i << 1 | 1;

		else i = i << 1;

	}

	return i - k - 1;

}

int getpro(int x)

{

	int i;

	for(i = x + k ; i ^ 1 ; i >>= 1)

		if(i & 1 && si[i >> 1] > si[i])

			break;

	if(i == 1) return -1;

	i ^= 1;

	while(i <= k)

	{

		if(si[i << 1 | 1]) i = i << 1 | 1;

		else i = i << 1;

	}

	return i - k - 1;

}

int getsub(int x)

{

	int i;

	for(i = x + k ; i ^ 1 ; i >>= 1)

		if(~i & 1 && si[i >> 1] > si[i])

			break;

	if(i == 1) return -1;

	i ^= 1;

	while(i <= k)

	{

		if(si[i << 1]) i = i << 1;

		else i = i << 1 | 1;

	}

	return i - k - 1;

}

int main()

{

	int n , m , opt , x;

	scanf("%d%d" , &n , &m);

	while(k <= n) k <<= 1;

	while(m -- )

	{

		scanf("%d" , &opt);

		switch(opt)

		{

			case 1: scanf("%d" , &x); if(!si[k + x + 1]) update(x + 1 , 1); break;

			case 2: scanf("%d" , &x); if(si[k + x + 1]) update(x + 1 , 0); break;

			case 3: printf("%d\n" , querymin()); break;

			case 4: printf("%d\n" , querymax()); break;

			case 5: scanf("%d" , &x) , printf("%d\n" , getpro(x + 1)); break;

			case 6: scanf("%d" , &x) , printf("%d\n" , getsub(x + 1)); break;

			default: scanf("%d" , &x) , printf("%d\n" , 2 * si[k + x + 1] - 1);

		}

	}

	return 0;

}

巴特西

【bzoj3685】普通van Emde Boas树权值zkw线段树

最新文章

热门文章

巴特西

【bzoj3685】普通van Emde Boas树 权值zkw线段树

最新文章

热门文章

【bzoj3685】普通van Emde Boas树权值zkw线段树