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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3545: [ONTAK2010]Peaks(离线+平衡树启发式合并)  

2014-04-24 12:52:00|  分类: 并查集,oi,bzoj, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


离线之后弄个并查集维护,然后平衡树启发式合并即可。


代码:

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

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

 

#define L( t ) Node[ t ].left

#define R( t ) Node[ t ].right

#define S( t ) Node[ t ].size

#define K( t ) Node[ t ].key

 

const int maxn = 100100 , maxm = 500100 , maxq = 500100 ;

 

struct node {

    int left , right , size , key ;

    node(  ) {

        left = right = size = 0 ;

    }

} Node[ maxn ] ;

 

void Left( int &t ) {

    int k = R( t ) ;

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

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

    t = k ;

}

 

void Right( 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( t ) ;

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

        return ;

    }

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

        Left( L( t ) ) ; Right( t ) ;

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

        return ;

    }

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

        Left( t ) ;

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

        return ;

    }

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

        Right( R( t ) ) ; Left( t ) ;

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

        return ;

    }

}

 

void Insert( int t , int &now ) {

    if ( ! now ) {

        now = t ; return ;

    }

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

    update( now ) ; maintain( now ) ;

}

 

int Select( int k , int now ) {

    if ( k == S( R( now ) ) ) return K( now ) ;

    if ( k < S( R( now ) ) ) return Select( k , R( now ) ) ;

    return Select( k - S( R( now ) ) - 1 , L( now ) ) ;

}

 

int Geta[ maxn ] , Getn ;

 

void Get( int now ) {

    if ( L( now ) ) Get( L( now ) ) ;

    if ( R( now ) ) Get( R( now ) ) ;

    L( now ) = R( now ) = 0 , S( now ) = 1 ;

    Geta[ ++ Getn ] = now ;

}

 

int Merge_bst( int u , int v ) {

    if ( S( u ) > S( v ) ) swap( u , v ) ;

    Getn = 0 ; Get( u ) ;

    for ( int i = 0 ; i ++ < Getn ; ) Insert( Geta[ i ] , v ) ;

    return v ;

}

 

int father[ maxn ] , root[ maxn ] ;

 

int Find( int x ) {

    int i = x , j = x , k ;

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

    for ( ; father[ j ] ; ) {

        k = father[ j ] ;

        father[ j ] = i ;

        j = k ;

    }

    return i ;

}

 

void Merge( int u , int v ) {

    int x = Find( u ) , y = Find( v ) ;

    if ( x == y ) return ;

    father[ x ] = y , root[ y ] = Merge_bst( root[ x ] , root[ y ] ) ;

}

 

struct itype {

    int x , y , v , t ;

    bool operator < ( const itype &a ) const {

        return v < a.v ;

    }

    void oper( int _x , int _y , int _v , int _t ) {

        x = _x , y = _y , v = _v , t = _t ;

    }

}  Q[ maxq ] , E[ maxm ] ;

 

int n , m , q , h[ maxn ] , ans[ maxq ] ;

 

int main(  ) {

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

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

        scanf( "%d" , h + i ) ;

        father[ i ] = 0 , root[ i ] = i ;

        S( i ) = 1 , K( i ) = h[ i ] ;

    }

    for ( int i = 0 ; i ++ < m ; ) {

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

        E[ i ].oper( s , t , v , 0 ) ;

    }

    for ( int i = 0 ; i ++ < q ; ) {

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

        Q[ i ].oper( v , k , x , i ) ;

    }

    sort( E + 1 , E + m + 1 ) , sort( Q + 1 , Q + q + 1 ) ;

    for ( int i = 1 , j = 0 ; i <= q ; ++ i ) {

        for ( ; j < m && E[ j + 1 ].v <= Q[ i ].v ; ++ j ) {

            Merge( E[ j + 1 ].x , E[ j + 1 ].y ) ;

        }

        int u = root[ Find( Q[ i ].x ) ] ;

        ans[ Q[ i ].t ] = S( u ) < Q[ i ].y ? ( - 1 ) : Select( Q[ i ].y - 1 , u ) ;

    }

    for ( int i = 0 ; i ++ < q ; ) printf( "%d\n" , ans[ i ] ) ;

    return 0 ;

}



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

历史上的今天

评论

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

页脚

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