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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3648: 寝室管理(点分治+平衡树)  

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

  下载LOFTER 我的照片书  |

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


首先这题求树或一个环套树上面的长度>=k的路径数,那么如果是树直接点分治掉没问题,考虑环套树的情况,如果路径在同一棵树上面,对所有树点分治即可,如果在环上,那么我们沿着顺时针方向扫两圈,平衡树维护一下,然后加加路径上新出现的点,再减掉消掉的点,然后平衡树整体加减一个数这个东西可以弄个时间戳记录一下,然后弄个delta维护即可,这样就平均每个点进平衡树1次,删掉1次,所以复杂度是O(n log^2 n + n log n)前面那个是点分的复杂度。


代码(长的233啊,还好码了一个多小时后就一A了,要不实在调不动):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cstdlib>

  •  

  • using namespace std ;

  •  

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

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

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

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

  •  

  • const int maxn = 101000 ;

  • const int maxm = 201000 ;

  • const int maxv = 401000 ;

  •  

  • struct edge {

  •         edge *next ;

  •         int t , v ;

  • } E[ maxm ] ;

  •  

  • edge *ept = E , *head[ maxn ] ;

  •  

  • inline void Init_edge(  ) {

  •         memset( head , 0 , sizeof( head ) ) ;

  • }

  •  

  • inline void add( int s , int t , int v ) {

  •         ept -> t = t , ept -> v = v , ept -> next = head[ s ] ; head[ s ] = ept ++ ;

  • }

  •  

  • inline void addedge( int s , int t , int v ) {

  •         add( s , t , v ) , add( t , s , v ) ;

  • }

  •  

  • int delta[ maxv ] , idx = 0 ;

  •  

  • struct node {

  •         int ky , mn , pr , sz ;

  •         node *lc , *rc ;

  •         inline void update(  ) {

  •                 sz = lc -> sz + rc -> sz + 1 ;

  •         }

  • } bst[ maxv ] ;

  •  

  • node *pt , *null , *root ;

  •  

  • inline void Init_bst(  ) {

  •         pt = bst ; null = pt ++ ;

  •         null -> lc = null -> rc = null , null -> pr = null -> sz = 0 ;

  •         root = null ;

  • }

  •  

  • inline void right( node* &t ) {

  •         node *k = t -> lc ;

  •         t -> lc = k -> rc ; t -> update(  ) ;

  •         k -> rc = t ; k -> update(  ) ;

  •         t = k ;

  • }

  •  

  • inline void left( node* &t ) {

  •         node *k = t -> rc ;

  •         t -> rc = k -> lc ; t -> update(  ) ;

  •         k -> lc = t ; k -> update(  ) ;

  •         t = k ;

  • }

  •  

  • void Insert( int key , node* &t ) {

  •         if ( t == null ) {

  •                 t = pt ++ ;

  •                 t -> lc = t -> rc = null , t -> sz = 1 , t -> ky = key , t -> mn = idx , t -> pr = rand(  ) ;

  •                 return ;

  •         }

  •         t -> sz ++ ;

  •         if ( key <= t -> ky + delta[ idx ] - delta[ t -> mn ] ) {

  •                 Insert( key , t -> lc ) ; if ( t -> lc -> pr > t -> pr ) right( t ) ;

  •         } else {

  •                 Insert( key , t -> rc ) ; if ( t -> rc -> pr > t -> pr ) left( t ) ;

  •         }

  • }

  •  

  • inline int Rank( int key , node *t ) {

  •         int rec = 0 ;

  •         for ( ; t != null ; ) {

  •                 if ( key <= t -> ky + delta[ idx ] - delta[ t -> mn ] ) {

  •                         rec += t -> rc -> sz + 1 ; t = t -> lc ;

  •                 } else t = t -> rc ;

  •         }

  •         return rec ;

  • }

  •  

  • void Delete( int key , node* &t ) {

  •         int k = t -> ky + delta[ idx ] - delta[ t -> mn ] ;

  •         if ( key == k ) {

  •                 if ( t -> lc == null ) {

  •                         t = t -> rc ; return ;

  •                 } else if ( t -> rc == null ) {

  •                         t = t -> lc ; return ;

  •                 } else if ( t -> lc -> pr > t -> rc -> pr ) {

  •                         right( t ) ; Delete( key , t -> rc ) ;

  •                 } else {

  •                         left( t ) ; Delete( key , t -> lc ) ;

  •                 }      

  •         } else if ( key < k ) Delete( key , t -> lc ) ; else Delete( key , t -> rc ) ;

  •         t -> update(  ) ;

  • }

  •  

  • bool used[ maxn ] , flag[ maxn ] ;

  • int n , m , k ;

  •  

  • typedef long long ll ;

  • ll ans = 0 ;

  •  

  • int sz[ maxn ] , dep[ maxn ] , rt , rv ;

  •  

  • #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

  •  

  • void gets( int now , int fa ) {

  •         sz[ now ] = 1 ;

  •         travel( now ) if ( p -> t != fa && ! flag[ p -> t ] && ! used[ p -> t ] ) {

  •                 gets( p -> t , now ) ; sz[ now ] += sz[ p -> t ] ;

  •         }

  • }

  •  

  • void getr( int now , int fa ) {

  •         bool Flag = ( sz[ rv ] - sz[ now ] ) <= ( sz[ rv ] >> 1 ) ;

  •         if ( Flag ) travel( now ) if ( p -> t != fa && ! flag[ p -> t ] && ! used[ p -> t ] ) {

  •                 if ( sz[ p -> t ] > ( sz[ rv ] >> 1 ) ) {

  •                         Flag = false ; break ;

  •                 }

  •         }

  •         if ( Flag ) rt = now ; else travel( now ) if ( p -> t != fa && ! flag[ p -> t ] && ! used[ p -> t ] ) {

  •                 getr( p -> t , now ) ;

  •                 if ( rt ) break ;

  •         }

  • }

  •  

  • int ch[ maxn ] , cn ;

  •  

  • void getc( int now , int fa ) {

  •         ch[ ++ cn ] = now , dep[ now ] = dep[ fa ] + 1 ;

  •         travel( now ) if ( p -> t != fa && ! used[ p -> t ] && ! flag[ p -> t ] ) getc( p -> t , now ) ;

  • }

  •  

  • void solve( int now ) {

  •         gets( now , 0 ) ;

  •         rt = 0 , rv = now ; getr( now , 0 ) ;

  •         dep[ rt ] = 0 ; Init_bst(  ) ; idx = 0 ; Insert( 1 , root ) ;

  •         travel( rt ) if ( ! flag[ p -> t ] && ! used[ p -> t ] ) {

  •                 cn = 0 ; getc( p -> t , rt ) ;

  •                 rep( i , cn ) ans += ll( Rank( k - dep[ ch[ i ] ] , root ) ) ;

  •                 rep( i , cn ) Insert( dep[ ch[ i ] ] + 1 , root ) ;

  •         }

  •         used[ rt ] = true ;

  •         travel( rt ) if ( ! flag[ p -> t ] && ! used[ p -> t ] ) solve( p -> t ) ;

  • }

  •  

  • int cv[ maxn ] , vn = 0 , sta[ maxn ] , tp = 0 , pos[ maxn ] ;

  •  

  • void dfs( int now , int v ) {

  •         sta[ pos[ now ] = ++ tp ] = now ;

  •         travel( now ) if ( p -> v != v ) {

  •                 if ( ! pos[ p -> t ] ) dfs( p -> t , p -> v ) ; else {

  •                         REP( i , pos[ p -> t ] , tp ) {

  •                                 flag[ cv[ vn ++ ] = sta[ i ] ] = true ;

  •                         }

  •                 }

  •                 if ( vn ) break ;

  •         }

  •         -- tp ;

  • }

  •  

  • int mes[ maxn ][ 2 ] ;

  •   

  • int main(  ) {

  •         srand( 12 ) ;

  •         Init_edge(  ) ;

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

  •         rep( i , m ) {

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

  •         }

  •         memset( flag , 0 , sizeof( flag ) ) , memset( used , false , sizeof( used ) ) ;

  •         if ( m == n - 1 ) {

  •                 solve( 1 ) ;

  •         } else {

  •                 memset( pos , 0 , sizeof( pos ) ) ; dfs( 1 , 0 ) ;

  •                 Rep( i , vn ) {

  •                         flag[ cv[ i ] ] = false ; solve( cv[ i ] ) ; flag[ cv[ i ] ] = true ;

  •                 }

  •                 Init_bst(  ) ; delta[ idx = 0 ] = 0 ;

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

  •                 rep( i , ( vn - 1 ) ) {

  •                         delta[ idx + 1 ] = delta[ idx ] + 1 ; ++ idx ;

  •                         dep[ cv[ i ] ] = 1 , ch[ cn = 1 ] = cv[ i ] ;

  •                         travel( cv[ i ] ) if ( ! flag[ p -> t ] ) getc( p -> t , cv[ i ] ) ;

  •                         rep( j , cn ) {

  •                                 Insert( dep[ ch[ j ] ] , root ) ;

  •                                 mes[ ch[ j ] ][ 0 ] = dep[ ch[ j ] ] , mes[ ch[ j ] ][ 1 ] = idx ;

  •                         }

  •                 }

  •                 Rep( i , vn ) {

  •                         dep[ cv[ i ] ] = 1 , ch[ cn = 1 ] = cv[ i ] ;

  •                         travel( cv[ i ] ) if ( ! flag[ p -> t ] ) getc( p -> t , cv[ i ] ) ;

  •                         rep( j , cn ) ans += ll( Rank( k - dep[ ch[ j ] ] , root ) ) ;

  •                         if ( i == vn - 1 ) break ;

  •                         delta[ idx + 1 ] = delta[ idx ] + 1 ; ++ idx ;

  •                         rep( j , cn ) Insert( dep[ ch[ j ] ] , root ) ;

  •                         cn = 0 ; getc( cv[ i + 1 ] , 0 ) ;

  •                         rep( j , cn ) Delete( mes[ ch[ j ] ][ 0 ] + delta[ idx ] - delta[ mes[ ch[ j ] ][ 1 ] ] , root ) ;

  •                 }

  •         }

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

  •         return 0 ; 

  • }



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

历史上的今天

评论

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

页脚

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