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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1018: [SHOI2008]堵塞的交通traffic(线段树)  

2014-03-18 20:56:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1018


用线段树维护区间的连通性,对于一个区间[L,R],维护的连通性如下图中加粗的连边表示:

BZOJ-1018: [SHOI2008]堵塞的交通traffic(线段树) - cjjlsdy - cjjlsdy的博客

然后就各种DT的分类讨论合并啦~


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define update( t I( t )=I(left( t ))+I(right( t ))

  •  

  • #define L( t ) L[ t ]

  • #define R( t ) R[ t ]

  • #define I( t ) I[ t ]

  •  

  • #define left( t )( t <<1)

  • #define right( t )(left( t )^1)

  •  

  • #define maxv ( maxn <<2)

  • #define maxn 100100

  •  

  • struct itype{

  •     int l , r ;

  •     bool f[6];

  •     itype(  ){

  •         memset( f ,false,sizeof( f ));

  •     }

  • };

  •  

  • bool road[ maxn ][3];

  •  

  • itype operator+(const itype &l ,const itype &r ){

  •     itype rec ;

  •     rec.l = l.l , rec.r = r.r ;

  •     rec.f[0]= l.f[0]||((( l.f[1]&& l.f[3])||( l.f[4]&& l.f[5]))&& road[ l.r ][0]&& road[ l.r ][1]&& r.f[0]);

  •     rec.f[1]=( l.f[1]&& road[ l.r ][0]&& r.f[1])||( l.f[4]&& road[ l.r ][1]&& r.f[5]);

  •     rec.f[2]= r.f[2]||((( r.f[1]&& r.f[3])||( r.f[4]&& r.f[5]))&& road[ l.r ][0]&& road[ l.r ][1]&& l.f[2]);

  •     rec.f[3]=( l.f[3]&& road[ l.r ][1]&& r.f[3])||( l.f[5]&& road[ l.r ][0]&& r.f[4]);

  •     rec.f[4]=( l.f[1]&& road[ l.r ][0]&& r.f[4])||( l.f[4]&& road[ l.r ][1]&& r.f[3]);

  •     rec.f[5]=( l.f[3]&& road[ l.r ][1]&& r.f[5])||( l.f[5]&& road[ l.r ][0]&& r.f[1]);

  •     return rec ;

  • }

  •  

  • int L[ maxv ], R[ maxv ];

  • itype I[ maxv ];

  •  

  • void build(int l ,int r ,int t ){

  •     L( t )= l ,R( t )= r ;

  •     if( l == r ){

  •         I( t ).f[1]=I( t ).f[3]=true,I( t ).l =I( t ).r = l ;

  •         return;

  •     }

  •     int mid =( l + r )>>1;

  •     build( l , mid ,left( t )),build( mid +1, r ,right( t ));

  •     update( t );

  • }

  •  

  • void change(int x ,int t ){

  •     if(L( t )==R( t )){

  •         I( t ).f[1]=I( t ).f[3]=true;

  •         I( t ).f[0]=I( t ).f[2]=I( t ).f[4]=I( t ).f[5]= road[L( t )][2];

  •         return;

  •     }

  •     int mid =(L( t )+R( t ))>>1;

  •     change( x , x <= mid ?left( t ):right( t ));

  •     update( t );

  • }

  •  

  • itype query(int l ,int r ,int t ){

  •     if( l ==L( t )&& r ==R( t ))return I( t );

  •     int mid =(L( t )+R( t ))>>1;

  •     if( r <= mid )return query( l , r ,left( t ));

  •     if( l > mid )return query( l , r ,right( t ));

  •     return query( l , mid ,left( t ))+query( mid +1, r ,right( t ));

  • }

  •  

  • int n ;

  •  

  • void Change(int x0 ,int y0 ,int x1 ,int y1 ,bool flag ){

  •     if( y0 > y1 )swap( x0 , x1 ),swap( y0 , y1 );

  •     if( x0 == x1 ){

  •         if( x0 ==1) road[ y0 ][0]= flag ;else road[ y0 ][1]= flag ;

  •     }else road[ y0 ][2]= flag ;

  •     change( y0 ,1);

  • }

  •  

  • bool Query(int x0 ,int y0 ,int x1 ,int y1 ){

  •     if( y0 > y1 )swap( x0 , x1 ),swap( y0 , y1 );

  •     itype templ =query(1, y0 ,1), tempm =query( y0 , y1 ,1), tempr =query( y1 , n ,1);

  •     if( x0 == x1 ){

  •         if( x0 ==1){

  •             if( tempm.f[1])return true;

  •             if((( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2]))&& tempm.f[3])return true;

  •         }else{

  •             if( tempm.f[3])return true;

  •             if((( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2]))&& tempm.f[1])return true;

  •         }

  •     }else{

  •         if( x0 ==1){

  •            if( tempm.f[4])return true;

  •             if( templ.f[2]&& tempm.f[3])return true;

  •             if( tempr.f[0]&& tempm.f[1])return true;

  •             if(( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2])&& tempm.f[5])return true;

  •         }else{

  •             if( tempm.f[5])return true;

  •             if( templ.f[2]&& tempm.f[1])return true;

  •             if( tempr.f[0]&& tempm.f[3])return true;

  •             if(( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2])&& tempm.f[4])return true;

  •         }

  •     }

  •     return false;

  • }

  •  

  • int main(  ){

  •     memset( road ,false,sizeof( road ));

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

  •     build(1, n ,1);

  •     char s[10];

  •     for(scanf("%s", s ); s[0]!='E';scanf("%s", s )){

  •         int x0 , y0 , x1 , y1 ;scanf("%d%d%d%d",&x0 ,&y0 ,&x1 ,&y1 );

  •         if( s[0]=='C'){

  •             Change( x0 , y0 , x1 , y1 ,false);

  •         }else if( s[0]=='O'){

  •             Change( x0 , y0 , x1 , y1 ,true);

  •         }else{

  •             printf(Query( x0 , y0 , x1 , y1 )?"Y\n":"N\n");

  •         }

  •     }

  •     return 0;

  • }


  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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