注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3685]普通van Emde Boas树  

2014-10-20 20:12:54|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3685: 普通van Emde Boas树

Time Limit: 9 Sec  Memory Limit: 128 MB
Submit: 233  Solved: 95
[Submit][Status]

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

HINT

Source

By Zky

Solution

写完跑样例然后1A也是醉了。。。

据说vEB tree是单次询问lglgn,看一下出题人的vEB tree跑得巨慢无比,直接去写zkw线段树了。

1、2、7都好说。

3、4的话,额外记录一下当前在集合内的数有几个

5、6如果要判-1的话,我的做法是,比如查前驱,在0~x-1的范围内查一下有多少个数。这样做好像会慢,我没想到更优的解法。

Code

没有缩行哟~

/**************************************************************
    Problem: 3685
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4508 ms
    Memory:8996 kb
****************************************************************/
 
#include<cstdio>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-48;
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-48;return aa;
}
int n,m,t[1<<21],d,o,now,op,x,l,r;
int main()
{
    for(n=F(),m=F(),d=1;d<n;d<<=1);
    for(;m--;)
    {
        op=F();
        if(op==1)
        {
            x=F();
            if(!t[d+x])
            {
                for(t[o=d+x]=1;o>>=1;t[o]++);now++;
            }
        }
        else if(op==2)
        {
            x=F();
            if(t[d+x])
            {
                for(t[o=d+x]=0;o>>=1;t[o]--);now--;
            }
        }
        else if(op==3)
        {
            if(!now)puts("-1");
            else
            {
                for(o=1;o<d;t[o<<=1]?1:o|=1);
                printf("%d\n",o-d);
            }
        }
        else if(op==4)
        {
            if(!now)puts("-1");
            else
            {
                for(o=1;o<d;t[(o<<=1)|1]?o|=1:1);
                printf("%d\n",o-d);
            }
        }
        else if(op==5)
        {
            x=F();
            for(l=d-1,r=x+d,o=0;l^r^1;l>>=1,r>>=1)
            ~l&1?o+=t[l^1]:1,r&1?o+=t[r^1]:1;
            if(o==0)puts("-1");
            else
            {
                for(o=x+d;(~o&1)||((o&1)&&!t[o^1]);o>>=1);
                for(o^=1;o<d;t[(o<<=1)|1]?o|=1:1);
                printf("%d\n",o-d);
            }
        }
        else if(op==6)
        {
            x=F();
            for(l=x+d,r=n+d,o=0;l^r^1;l>>=1,r>>=1)
            ~l&1?o+=t[l^1]:1,r&1?o+=t[r^1]:1;
            if(o==0)puts("-1");
            else
            {
                for(o=x+d;(o&1)||((~o&1)&&!t[o^1]);o>>=1);
                for(o^=1;o<d;t[o<<=1]?1:o|=1);
                printf("%d\n",o-d);
            }
        }
        else if(op==7)
        {
            puts(t[F()+d]?"1":"-1");
        }
    }
}
  评论这张
 
阅读(83)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018