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

ydc的博客

 
 
 

日志

 
 

bzoj 1018  

2013-02-04 21:14:11|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

深深感受到自己的线段树能力太弱了!!!!

这道题是个线段树,他要维护6个域!!!

假设是[l,r]区间,要维护这段区间的四个角落的联通性,所以共有六种联通情况都要维护下来。

区间合并时,可以通过 “左儿子的6个域” 与 “右儿子的6个域” 与 “ 左儿子右端点和右儿子左端点之间” 是否有边 ,得到 此区间 的联通情况。

具体的递推式非常麻烦但也非常锻炼能力,大家可以自己推推一定能推出来的。

然后是查询:

要分四种情况……

得到[1,l-1]区间联通性,[l,r]区间联通性,[r+1,n]之间联通性。

情况一:[l,r]里,l,r联通

情况二:不妨设他在(l,0),路线是(l,0)->(l-1,0)->(l-1,1)->(l,1)->r,这就要求l-1与l之间上下都有边并且(l-1,0)与(l-1,1)联通。如果他在(l,1),方案相反

情况三:不妨设他在(r,0),路线是(r,0)->(r+1,0)->(r+1,1)->(r,1)->l,与情况二类似。他在(r,1)方案相反

情况四:由于上面的两个情况带了个头,我就不将那么详细了,大概就是从l向左走到1绕到l再走到n再绕下来再走到r

然后吐槽一下bzoj上题目(可能就是jsoi原题)描述极其不清,(r1,r2)表示第r1行r2列,这在题目描述中不仅没提到连给我们推断一下的信息都没有

最后赞扬一下,这道题真的是线段树好题啊!像我这种只做过线段树裸题的真的自惭形秽……相比起来我以前做的都是什么啊!区间乘一个数区间加一个数区间置为一个数区间极值区间求和…………顶多综合一下几个操作,比起这道题来,实在是太弱了。

代码中有一些方便理解的注释,所以长度也增加了

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 400010
#define now tree[root]
#define lson tree[root*2]
#define rson tree[root*2+1]
using namespace std;
struct node
{
    bool p1,p2,p3,p4,p5,p6;
    /*
        p1:(1,0)->(1,1)
        p2:(1,0)->(0,0)
        p3:(1,0)->(0,1)
        p4:(0,0)->(1,1)
        p5:(0,0)->(0,1)
        p6:(1,1)->(0,1)
    */
};
struct Seg
{
    int left,right;
    node p;
}tree[MAXN];
int n;
bool edge[MAXN][2];
void Build(int root,int l,int r)
{
    now.left=l,now.right=r;
    int mid=(l+r)>>1;
    if(l==r)
    {
        now.p.p1=now.p.p5=true;
        return ;
    }
    Build(root*2,l,mid),Build(root*2+1,mid+1,r);
}
void read()
{
    scanf("%d",&n);
    Build(1,1,n);
}
node update(const node &l,const node &r,int k)
{
    node ans;
    ans.p1=(l.p1&edge[k][1]&r.p1)|(l.p3&edge[k][0]&r.p4);
    ans.p2=l.p2|(l.p1&edge[k][1]&r.p2&edge[k][0]&l.p5);
    ans.p3=(l.p1&edge[k][1]&r.p3)|(l.p3&edge[k][0]&r.p5);
    ans.p4=(l.p4&edge[k][1]&r.p1)|(l.p5&edge[k][0]&r.p4);
    ans.p5=(l.p4&edge[k][1]&r.p3)|(l.p5&edge[k][0]&r.p5);
    ans.p6=r.p6|(r.p1&edge[k][1]&l.p6&edge[k][0]&r.p5);
    return ans;
}
void work(int root,int a,int b,int c,int d,bool k)
{
    /*
        p1:(1,0)->(1,1)
        p2:(1,0)->(0,0)
        p3:(1,0)->(0,1)
        p4:(0,0)->(1,1)
        p5:(0,0)->(0,1)
        p6:(1,1)->(0,1)
    */
    if(now.left==a&&now.right==c)
    {
        if(a==c&&abs(b-d)==1)  now.p.p2=now.p.p3=now.p.p4=now.p.p6=k;
        if(a==c-1)  now.p=update(lson.p,rson.p,lson.right);
        return ;
    }
    int mid=(now.left+now.right)>>1;
    if(c<=mid)  work(root*2,a,b,c,d,k);
    else if(mid<a)  work(root*2+1,a,b,c,d,k);
    now.p=update(lson.p,rson.p,lson.right);
}
node Find(int root,int l,int r)
{
    if(now.left==l&&now.right==r)  return now.p;
    int mid=(now.left+now.right)>>1;
    if(r<=mid)  return Find(root*2,l,r);
    else if(mid<l)  return Find(root*2+1,l,r);
    else return update(Find(root*2,l,mid),Find(root*2+1,mid+1,r),mid);
}
char Query(int a,int b,int c,int d)
{
    /*
        p1:(1,0)->(1,1)
        p2:(1,0)->(0,0)
        p3:(1,0)->(0,1)
        p4:(0,0)->(1,1)
        p5:(0,0)->(0,1)
        p6:(1,1)->(0,1)
    */
    if(a==c&&b==d)  return true;
    if(a>c)  swap(a,c),swap(b,d);
    node ans1,ans2=Find(1,a,c),ans3;
    if(a>1)  ans1=Find(1,1,a-1);
    if(c<n)  ans3=Find(1,c+1,n);
    /*Part1*/
    if(a==c&&ans2.p2)  return true;
    if(a!=c&&b==1&&d==1&&ans2.p1)  return true;
    if(a!=c&&b==1&&d==0&&ans2.p3)  return true;
    if(a!=c&&b==0&&d==1&&ans2.p4)  return true;
    if(a!=c&&b==0&&d==0&&ans2.p5)  return true;
    /*Part2*/
    if(a>1&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&a==c)  return true;
    if(a>1&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&b==0&&d==0&&ans2.p3)  return true;
    if(a>1&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&b==0&&d==1&&ans2.p1)  return true;
    if(a>1&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&b==1&&d==0&&ans2.p5)  return true;
    if(a>1&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&b==1&&d==1&&ans2.p4)  return true;
    /*Part3*/
    if(c<n&&edge[c][0]&&edge[c][1]&&ans3.p2&&a==c)  return true;
    if(c<n&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==0&&d==0&&ans2.p4)  return true;
    if(c<n&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==0&&d==1&&ans2.p5)  return true;
    if(c<n&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==1&&d==0&&ans2.p1)  return true;
    if(c<n&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==1&&d==1&&ans2.p3)  return true;
    /*Part4*/
    if(a>1&&c<n&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&edge[c][0]&&edge[c][1]&&ans3.p2&&a==c)  return true;
    if(a>1&&c<n&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==0&&d==0&&ans2.p1)  return true;
    if(a>1&&c<n&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==0&&d==1&&ans2.p3)  return true;
    if(a>1&&c<n&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==1&&d==0&&ans2.p4)  return true;
    if(a>1&&c<n&&edge[a-1][0]&&edge[a-1][1]&&ans1.p6&&edge[c][0]&&edge[c][1]&&ans3.p2&&b==1&&d==1&&ans2.p5)  return true;
    return false;
}
void Ask()
{
    char task[10];
    int a,b,c,d;
    while(scanf("%s",task)&&strcmp(task,"Exit"))
    {
        scanf("%d %d %d %d",&b,&a,&d,&c);
        if(strcmp(task,"Open")==0)
        {
            if(a>c)  swap(a,c),swap(b,d);
            if(a==c-1)  edge[a][b-1]=true;
            work(1,a,b-1,c,d-1,true);
        }
        if(strcmp(task,"Close")==0)
        {
            if(a>c)  swap(a,c),swap(b,d);
            if(a==c-1)  edge[a][b-1]=false;
            work(1,a,b-1,c,d-1,false);
        }
        if(strcmp(task,"Ask")==0)  printf("%c\n",Query(a,b-1,c,d-1)?'Y':'N');
    }
}
int main()
{
    read();
    Ask();
    return 0;
}

 


  评论这张
 
阅读(1345)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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