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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2733: [HNOI2012]永无乡(SBT+并查集+启发式合并)  

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

  下载LOFTER 我的照片书  |

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


实在是被动态规划虐的体无完肤了(CF上一道状压调了好久都没写出来QaQ),只能过来继续水数据结构了。

思路很明显,既然是k最值,那就平衡树或者是权值线段树维护一下,然后要维护连通性,就用并查集维护,至于树的合并问题,每次把小的那棵树暴力合并到大的里面就好啦(启发式合并,这个操作是均摊O(n log n)的,算上插入O( log n )的复杂度就是O( n log^2 n ),为什么?想想并查集的按rank合并就可以啦~)


代码(SBT+并查集+启发式合并):

BZOJ-2733: [HNOI2012]永无乡(SBT+并查集+启发式合并) - cjjlsdy - cjjlsdy的博客

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define MAXN 100010

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define K( t ) key[ t ]

  • #define S( t ) size[ t ]

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

  •  

  • int left[ MAXN ], right[ MAXN ], key[ MAXN ], size[ MAXN ], n , m , q ;

  •  

  • void left_ratote(int&t ){

  •     int k =R( t );

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

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

  •     t = k ;

  • }

  •  

  • void right_ratote(int&t ){

  •     int k =L( t );

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

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

  •     t = k ;

  • }

  •  

  • void maintain(int&t ){

  •     if(S(L(L( t )))>S(R( t ))){

  •         right_ratote( t );

  •         maintain(R( t ));maintain( t );

  •         return;

  •     }

  •     if(S(R(R( t )))>S(L( t ))){

  •         left_ratote( t );

  •         maintain(L( t ));maintain( t );

  •         return;

  •     }

  •     if(S(R(L( t )))>S(R( t ))){

  •         left_ratote(L( t ));right_ratote( t );

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

  •         return;

  •     }

  •     if(S(L(R( t )))>S(L( t ))){

  •         right_ratote(R( t ));left_ratote( t );

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

  •         return;

  •     }

  • }

  •  

  • void Insert(int u ,int&t ){

  •     if(! t ){

  •         t = u ;

  •         L( t )=R( t )=0,S( t )=1;

  •         return;

  •     }

  •     Insert( u ,K( u )<K( t )?L( t ):R( t ));

  •     update( t );maintain( t );

  • }

  •  

  • int Rank(int k ,int t ){

  •     if(S( t )<= k ||! t )return -1;

  •     if( k ==S(L( t )))return t ;

  •     return k <S(L( t ))?Rank( k ,L( t )):Rank( k -S(L( t ))-1,R( t ));

  • }

  •  

  • int father[ MAXN ], roof[ MAXN ];

  •  

  • int find_roof(int t ){

  •     int i = t , j = t ;

  •     for(; father[ i ]; i = father[ i ]);

  •     while( father[ j ]){

  •         int k = father[ j ];

  •         father[ j ]= i ;

  •         j = k ;

  •     }

  •     return i ;

  • }

  •  

  • int dfn[ MAXN ], cnt ;

  •  

  • void dfs(int t ){

  •     dfn[++ cnt ]= t ;

  •     if(L( t ))dfs(L( t ));

  •     if(R( t ))dfs(R( t ));

  • }

  •  

  • void Union(int u ,int t ){

  •     int k =find_roof( u ), v =find_roof( t );

  •     if( k == v )return;

  •     if(S( roof[ k ])>S( roof[ v ]))swap( k , v );

  •     cnt =0;dfs( roof[ k ]);

  •     for(int i =0; i ++< cnt ;)Insert( dfn[ i ], roof[ v ]);

  •     father[ k ]= v ;

  • }

  •  

  • int main(  ){

  •     L(0)=R(0)=S(0)=0;

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

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

  •         scanf("%d",&K( i ));

  •         L( i )=R( i )=0,S( i )=1, roof[ i ]= i ;

  •     }

  •     while( m --){

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

  •         Union( s , t );

  •     }

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

  •     while( q --){

  •         int ch ;for( ch =getchar(  );!( ch >='A'&& ch <='Z'); ch =getchar(  ));

  •         if( ch =='B'){

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

  •             Union( s , t );

  •         }else{

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

  •             printf("%d\n",Rank( k -1, roof[find_roof( x )]));

  •         }

  •     }

  •     return 0;

  • }


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

历史上的今天

评论

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

页脚

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