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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1095: [ZJOI2007]Hide 捉迷藏(括号序列+线段树)  

2014-03-25 21:32:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


这道题可以用动态树分治水过去,但是代码量相当大,于是乎我偷懒用了括号序列的写法,好不容易A掉了额。(神奇的传送门:http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-%E6%8D%89%E8%BF%B7%E8%97%8F/


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define AddEdge( s , t Add( s , t ),Add( t , s )

  • #define Add( s , t ) E[ s ].push_back( t )

  •  

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

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

  •  

  • #define L( t ) Left[ t ]

  • #define R( t ) Right[ t ]

  • #define LP( t ) left_push[ t ]

  • #define RP( t ) right_push[ t ]

  • #define LM( t ) left_minus[ t ]

  • #define RM( t ) right_minus[ t ]

  • #define D( t ) Dist[ t ]

  • #define A( t ) la[ t ]

  • #define B( t ) rb[ t ]

  •  

  • #define rep( i , x for(int i =0; i ++< x ;)

  • #define travel( x for( vector <int>:: iterator p = E[ x ].begin(  ); p != E[ x ].end(  );++ p )

  •  

  • const int maxn =101000;

  • const int inf =1000000000;

  • const int maxv = maxn <<3;

  •  

  • vector <int> E[ maxn ];

  •  

  • int n , m , in[ maxn ], out[ maxn ], dfn[ maxn <<1], num[ maxn <<1], Index =0;

  • bool col[ maxn <<1];

  •  

  • void dfs(int v ,int u ){

  •     num[ in[ v ]=++ Index ]=0;

  •     travel( v )if(*p != u )dfs(*p , v );

  •     num[ out[ v ]=++ Index ]=1;

  • }

  •  

  • int left_push[ maxv ], right_push[ maxv ], left_minus[ maxv ], right_minus[ maxv ];

  • int Left[ maxv ], Right[ maxv ], Dist[ maxv ], la[ maxv ], rb[ maxv ];

  •  

  • void update(int t ){

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

  •         if(B(left( t ))>A(right( t ))){

  •             A( t )=A(left( t ));

  •             B( t )=B(right( t ))+B(left( t ))-A(right( t ));

  •         }else{

  •             A( t )=A(left( t ))+A(right( t ))-B(left( t ));

  •             B( t )=B(right( t ));

  •         }

  •         LP( t )=max(LP(left( t )),max(A(left( t ))-B(left( t ))+LP(right( t )),A(left( t ))+B(left( t ))+LM(right( t ))));

  •         LM( t )=max(LM(left( t )),B(left( t ))-A(left( t ))+LM(right( t )));

  •         RP( t )=max(RP(right( t )),max(A(right( t ))+B(right( t ))+RM(left( t )),B(right( t ))-A(right( t ))+RP(left( t ))));

  •         RM( t )=max(RM(right( t )),A(right( t ))-B(right( t ))+RM(left( t )));

  •         D( t )=max(max(D(left( t )),D(right( t ))),max(RM(left( t ))+LP(right( t )),RP(left( t ))+LM(right( t ))));

  •     }

  • }

  •  

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

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

  •     if( l == r ){

  •         A( t )= num[ l ]==1?1:0;

  •         B( t )= num[ l ]==0?1:0;

  •         if(! col[ r +1]){

  •             LP( t )=A( t )+B( t );

  •             LM( t )=B( t )-A( t );

  •         }else{

  •             LP( t )=LM( t )=- inf ;

  •         }

  •         if(! col[ l -1]){

  •             RP( t )=A( t )+B( t );

  •             RM( t )=A( t )-B( t );

  •         }else{

  •             RP( t )=RM( t )=- inf ;

  •         }

  •         if(! col[ l -1]&&! col[ r +1]){

  •             D( t )=1;

  •         }else D( t )=- inf ;

  •         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 )){

  •         if(! col[ x +1]){

  •             LP( t )=A( t )+B( t );

  •             LM( t )=B( t )-A( t );

  •         }else{

  •             LP( t )=LM( t )=- inf ;

  •         }

  •         if(! col[ x -1]){

  •             RP( t )=A( t )+B( t );

  •             RM( t )=A( t )-B( t );

  •         }else{

  •             RP( t )=RM( t )=- inf ;

  •         }

  •         if(! col[ x -1]&&! col[ x +1]){

  •             D( t )=1;

  •         }else D( t )=- inf ;

  •         return;

  •     }

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

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

  •     update( t );

  • }

  •  

  • void Change(int v ){

  •     col[ in[ v ]]^=true;

  •     if( in[ v ]-1)change( in[ v ]-1,1);

  •     if( in[ v ]<( n <<1))change( in[ v ]+1,1);

  •     col[ out[ v ]]^=true;

  •     if( out[ v ]-1)change( out[ v ]-1,1);

  •     if( out[ v ]<( n <<1))change( out[ v ]+1,1);

  • }

  •  

  • int main(  ){

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

  •     rep( i , n -1){

  •         int s , t ;scanf("%d%d",&s ,&t );

  •         AddEdge( s , t );

  •     }

  •     dfs(1,0);

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

  •     col[0]= col[( n <<1)+1]=true;

  •     build(1, n <<1,1);

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

  •     while( m --){

  •         int ch ;for( ch =getchar(  ); ch !='G'&& ch !='C'; ch =getchar(  ));

  •         if( ch =='C'){

  •             int v ;scanf("%d",&v );

  •             Change( v );

  •         }else printf("%d\n",D(1));

  •     }

  •     return 0;

  • }



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

历史上的今天

评论

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

页脚

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