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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3192: [JLOI2013]删除物品(splay)  

2014-01-11 22:00:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


直接splay和优先队列暴力维护即可,记得n1=0,n2=0的特判。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <queue>

  •  

  • using namespace std ;

  •  

  • #define MAXN 100010

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define F( t ) father[ t ]

  • #define G( t )F(F( t ))

  • #define S( t ) size[ t ]

  • #define T( t ) tag[ t ]

  • #define clear( t )memset( t ,0,sizeof( t ))

  • #define C( t )( t ==L(F( t )))

  • #define update( t )S( t )=S(L( t ))+S(R( t ))+1

  • #define ll long long

  •  

  • struct Object{

  •             int v , t ;

  •             bool operator<(const Object &a )const{

  •                         return v < a.v ;

  •             }

  •             Object(int _v ,int _t ):v ( _v ),t ( _t ){

  •             }

  • };

  • priority_queue < Object > Q ;

  •  

  • int left[ MAXN ], right[ MAXN ], father[ MAXN ], size[ MAXN ];

  • bool tag[ MAXN ];

  •  

  • void Init(  ){

  •             clear( left ),clear( right ),clear( father ),clear( size ),clear( tag );

  • }

  •  

  • void pushdown(int t ){

  •             if(T( t )&& t ){

  •                         swap(L( t ),R( t ));

  •                         T(L( t ))^=true,T(R( t ))^=true,T( t )^=true;

  •             }

  • }

  •  

  • void zag(int t ){

  •             pushdown( t );pushdown(R( t ));

  •             int k =R( t ), u =F( t );bool flag =C( t );

  •             F(R( t )=L( k ))= t ;update( t );

  •             F(L( k )= t )= k ;update( k );

  •             F( k )= u ;if( u )if( flag )L( u )= k ;else R( u )= k ;

  • }

  •  

  • void zig(int t ){

  •             pushdown( t );pushdown(L( t ));

  •             int k =L( t ), u =F( t );bool flag =C( t );

  •             F(L( t )=R( k ))= t ;update( t );

  •             F(R( k )= t )= k ;update( k );

  •             F( k )= u ;if( u )if( flag )L( u )= k ;else R( u )= k ;

  • }

  •  

  • void splay(int t ){

  •             while(F( t )){

  •                         pushdown(G( t ));pushdown(F( t ));pushdown( t );

  •                         if(!G( t ))if(C( t ))zig(F( t ));else zag(F( t ));else{

  •                                      if(C( t )){

  •                                                  if(C(F( t )))zig(G( t ));zig(F( t ));

  •                                      }else{

  •                                                  if(!C(F( t )))zag(G( t ));zag(F( t ));

  •                                      }

  •                         }

  •             }

  • }

  •  

  • int Min(int t ){

  •             pushdown( t );

  •             while(L( t ))pushdown( t =L( t ));

  •             return t ;

  • }

  •  

  • int n1 , n2 , top1 , top2 ;

  • ll ans =0;

  •  

  • int main(  ){

  •             Init(  );

  •             scanf("%d%d",&n1 ,&n2 );

  •             for(int i =0; i ++< n1 ;){

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

  •                         Q.push(Object( x , i ));

  •                         S( i )=1;

  •             }

  •             for(int i =0; i ++< n2 ;){

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

  •                         Q.push(Object( x , n1 + i ));

  •                         S( i + n1 )=1;

  •             }

  •             for(int i =1; i ++< n1 ;){

  •                         splay( i -1);

  •                         F(R( i -1)= i )= i -1;update( i -1);

  •             }

  •             if( n1 )F(R( n1 )= n1 + n2 +1)= n1 ;

  •             if( n2 )F(R( n1 + n2 )= n1 + n2 +2)= n1 + n2 ;

  •             S( n1 + n2 +1)=S( n1 + n2 +2)=1;

  •             top1 =1, top2 = n1 +1;

  •             if(! n1 ) top1 = n1 + n2 +1;

  •             if(! n2 ) top2 = n1 + n2 +2;

  •             for(int i =1; i ++< n2 ;){

  •                         splay( n1 + i -1);

  •                         F(R( n1 + i -1)= n1 + i )= n1 + i -1;update( n1 + i -1);

  •             }

  •             for(int i =0; i ++< n1 + n2 ;){

  •                         Object v = Q.top(  ); Q.pop(  );

  •                         splay( v.t );pushdown( v.t ); ans +=S(L( v.t ));

  •                         if(Min( v.t )== top1 ){

  •                                      splay( top2 );

  •                                      T(L( v.t ))^=true;

  •                                      F(L( top2 )=L( v.t ))= top2 ;update( top2 );

  •                                      top2 =Min( top2 );splay( top2 );

  •                                      F( top1 =R( v.t ))=0; top1 =Min( top1 );

  •                                      splay( top1 );

  •                         }else{

  •                                      splay( top1 );

  •                                      T(L( v.t ))^=true;

  •                                      F(L( top1 )=L( v.t ))= top1 ;update( top1 );

  •                                      top1 =Min( top1 );splay( top1 );

  •                                      F( top2 =R( v.t ))=0; top2 =Min( top2 );

  •                                      splay( top2 );

  •                         }

  •             }

  •             printf("%lld\n", ans );

  •             return ;

  • }



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

历史上的今天

评论

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

页脚

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