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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3249: [ioi2013]game(动态线段树套SBT)  

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

  下载LOFTER 我的照片书  |

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

官方题目和数据:http://www.ioi2013.org/competition/tasks/


刚开始以为怎么这么一道傻叉数据结构题怎么没有什么人去写,不就一裸线段树套线段树,或者线段树(动态建树)套平衡树,还是平衡树套平衡树还是线段树神马的啊,然后就开始狂码上半天sgt+splay,交上去,果断TLE,然后又试了各种常数优化,IO优化神马的都上了,还要跑了260s+(交了好几次,差不多总共TLE了5次,卡20min左右,BZOJ上的同学们对不起啊),BZOJ的时限只有250s,最后无语的把splay改成SBT一次就A了,快了一倍左右。(Splay树的巨大常数说多了都是泪啊。。。以后不是那种要翻转的区间维护我是不会写splay的就是了。。。)

NOI官网上的IOI题解里大神的题解说是trie套trie,太神奇实在没想通,trie树居然还有这种神奇功能(孤陋寡闻啊我)。


代码(百度空间脑残了,贴不了这么长的高亮代码,贴代码的功能高亮又不知道哪里去了。。。QaQ):

BZOJ-3249: [ioi2013]game(动态线段树套SBT) - cjjlsdy - cjjlsdy的博客

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define MAXN 3000100

#define L( t ) left[ t ]

#define R( t ) right[ t ]

#define Gcd( t ) Gcd[ t ]

#define Max( t ) Max[ t ]

#define Min( t ) Min[ t ]

#define V( t ) value[ t ]

#define K( t ) key[ t ]

#define S( t ) size[ t ]

#define inf 0x7fffffff

#define ll long long

 

void getint( int &t ) {

    int ch ; for ( ch = getchar(  ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar(  ) ) ;

    t = ch - '0' ;

    for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) t *= 10 , t += ch - '0' ;

}

  

void getll( ll &t ) {

    int ch ; for ( ch = getchar(  ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar(  ) ) ;

    t = ch - '0' ;

    for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) t *= 10 , t += ch - '0' ;

}

  

int ans[ 20 ] ;

  

void putll( ll t ) {

    if ( ! t ) putchar( '0' ) ; else {

        ans[ 0 ] = 0 ;

        for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;

        while ( ans[ 0 ] ) putchar( '0' + ans[ ans[ 0 ] -- ] ) ;

    }

    putchar( '\n' ) ;

}

 

struct Pos {

    int x , y ;

    bool operator < ( const Pos &a ) const {

        return y < a.y || ( y == a.y && x < a.x ) ;

    }

    bool operator == ( const Pos &a ) const {

        return x == a.x && y == a.y ;

    }

    bool operator > ( const Pos &a ) const {

        return y > a.y ||( y == a.y && x > a.x ) ;

    }

} key[ MAXN ] , Max[ MAXN ] , Min[ MAXN ] ;

 

Pos make( int _x , int _y ) {

    Pos u ; u.x = _x , u.y = _y ;

    return u ;

}

 

int left[ MAXN ] , right[ MAXN ] , size[ MAXN ] , Node = 0 ;

ll value[ MAXN ] , Gcd[ MAXN ] ;

 

ll gcd( ll x , ll y ) {

    if ( x < y ) swap( x , y ) ;

    ll k ;

    while ( y ) {

        k = y ;

        y = x % y ;

        x = k ;

    }

    return x ;

}

 

void update( int t ) {

    if ( ! t ) return ;

    Gcd( t ) = gcd( gcd( Gcd( L( t ) ) , Gcd( R( t ) ) ) , V( t ) ) ;

    S( t ) = S( L( t ) ) + S( R( t ) ) + 1 ;

    Max( t ) = R( t ) ? Max( R( t ) ) : K( t ) ;

    Min( t ) = L( t ) ? Min( L( t ) ) : K( t ) ;

}

 

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( Pos k , ll v , int &t ) {

    if ( ! t ) {

        t = ++ Node ;

        S( t ) = 1 , L( t ) = R( t ) = 0 , V( t ) = Gcd( t ) = v , K( t ) = Max( t ) = Min( t ) = k ;

        return ;

    }

    if ( k == K( t ) ) {

        V( t ) = v ; update( t ) ; return ;

    }

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

    update( t ) ; maintain( t ) ;

}

 

ll query( Pos l , Pos r , int t ) {

    if ( ! t ) return 0 ;

    if ( ! ( Min[ t ] < l ) && ! ( Max[ t ] > r ) ) return Gcd( t ) ;

    if ( r < K( t ) ) return query( l , r , L( t ) ) ;

    if ( l > K( t ) ) return query( l , r , R( t ) ) ;

    ll rec = V( t ) ;

    if ( l < K( t ) ) rec = gcd( rec , query( l , Max[ L( t ) ] , L( t ) ) ) ;

    if ( r > K( t ) ) rec = gcd( rec , query( Min[ R( t ) ] , r , R( t ) ) ) ;

    return rec ;

}

 

struct Node_sgt {

    Node_sgt *left , *right ;

    int roof ;

} *sgt , *null = new( Node_sgt ) ;

 

void Init_sgt_sbt(  ) {

    sgt = null -> left = null -> right = null , null -> roof = 0 ;

    L( 0 ) = R( 0 ) = S( 0 ) = V( 0 ) = Gcd( 0 ) = 0 , Max( 0 ) = make( - inf , - inf ) , Min( 0 ) = make( inf , inf ) ;

}

 

void Change( int l , int r , int x , int y , ll v , Node_sgt *&t ) {

    if ( t == null ) {

        t = new( Node_sgt ) ;

        t -> left = t -> right = null , t -> roof = 0 ;

    }

    Insert( make( x , y ) , v , t -> roof ) ;

    if ( l == r ) return ;

    int mid = ( l + r ) >> 1 ;

    if ( x <= mid ) Change( l , mid , x , y , v , t -> left ) ; else

    Change( mid + 1 , r , x , y , v , t -> right ) ;

}

 

ll Query( int l , int r , int x0 , int y0 , int x1 , int y1 , Node_sgt *t ) {

    if ( l == x0 && r == x1 ) return query( make( x0 , y0 ) , make( x1 , y1 ) , t -> roof ) ;

    int mid = ( l + r ) >> 1 ;

    if ( x1 <= mid ) return Query( l , mid , x0 , y0 , x1 , y1 , t -> left ) ;

    if ( x0 > mid ) return Query( mid + 1 , r , x0 , y0 , x1 , y1 , t -> right ) ;

    return gcd( Query( l , mid , x0 , y0 , mid , y1 , t -> left ) , Query( mid + 1 , r , mid + 1 , y0 , x1 , y1 , t -> right ) ) ;

}

 

int n , m , q ;

 

int main(  ) {

    Init_sgt_sbt(  ) ;

    getint( n ) , getint( m ) , getint( q ) ;

    while ( q -- ) {

        int x ; getint( x ) ;

        if ( x == 1 ) {

            int px , py ; ll pv ; getint( px ) , getint( py ) ; getll( pv ) ;

            Change( 0 , n - 1 , px , py , pv , sgt ) ;

        } else {

            int x0 , x1 , y0 , y1 ; getint( x0 ) , getint( y0 ) , getint( x1 ) , getint( y1 ) ;

            putll( Query( 0 , n - 1 , x0 , y0 , x1 , y1 , sgt ) ) ;

        }

    }

    return 0 ;

}


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

历史上的今天

评论

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

页脚

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