首页 > 代码库 > 【bzoj3685】普通van Emde Boas树 权值zkw线段树
【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线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。