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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2877: [Noi2012]魔幻棋盘(线段树)  

2014-06-24 18:34:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


嗯,这次好好写一次题解吧,这题傻叉的写了半天QAQ    :

首先,由欧几里德算法,我们知道gcd(a,b)=gcd(a,abs(a-b)),所以:

令G(ai)=gcd(a1,a2,...ai...,an)则,G(ai)=gcd(a1,a2-a1,...,an-a(n-1)),所以对于矩阵[l,r,x,y](表示矩阵四个顶点中,最小的行数为l,最大为r,最小的列数为x,最大的为y),设题目中的定点为(px,py),则答案为:

G(a(i,j))(l<=i<=r,x<=j<=y)

=G( G(a(i,j)(x<=j<=y) ) (l<=i<=r)

=G(  gcd( G(  a(  i , j  ) - a( i , j - 1 )  ) , a( i , py ) ) ( x < j <= y )  ) ( l <= i <= r )

=gcd( G(  G( a( i , j ) - a( i , j - 1 ) ) ( l <= i <= r )  ) ( x < j <= y )  , G( a( i , py ) ) ( l <= i <= r )  )

那么拆一下:

G( a( i , py ) ) ( l <= i <= r )  = gcd( a( px , py ) , G( a( i , py ) - a( i - 1 , py ) ) ( l < i <= r )  )

G( G(  a( i , j ) - a( i , j - 1 )  ) ) ( l <= i <= r ) ( x < j <= y )

= G(  gcd(  a(  px , j  )  - a( px , j - 1 ) , G( [ a( i , j ) - a( i , j - 1 ) ] - [ a( i - 1 , j ) - a( i - 1 , j - 1 ) ] ) ( l < i <= r )  )  )( x < j <= y )

= gcd(     G(  a( px , j ) - a( px , j - 1 )  ) ( x < j <= y )   , G( a( i , j ) - a( i , j - 1 ) - a( i - 1 , j ) + a( i - 1 ,  j - 1 ) )( l < i <= r && x < j <= y )    )

然后,用两棵一维线段树维护G( a( i , py ) - a( i - 1 , py ) ) ( l < i <= r )   , G(  a( px , j ) - a( px , j - 1 )  ) ( x < j <= y ) ,用一棵二维线段树维护G( a( i , j ) - a( i , j - 1 ) - a( i - 1 , j ) + a( i - 1 ,  j - 1 ) )( l < i <= r && x < j <= y ) ,我们神奇的发现每次修改操作在这三棵线段树上都是单点修改,然后就可以AC了。

时间复杂度:O(n log^3 n)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • 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 Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  •  

  • const int maxn = 501000 ;

  •  

  • typedef long long ll ;

  •  

  • ll gcd( ll x , ll y ) {

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

  •     for ( ll t ; y ; t = y , y = x % y , x = t ) ;

  •     return x ;

  • }

  •  

  • struct node {

  •      

  •     int l , r , mid ;

  •     ll g ;

  •     node *lc , *rc ;

  •      

  •     inline void update(  ) {

  •         g = gcd( abs( lc -> g ) , abs( rc -> g ) ) ;

  •     }

  •      

  • } sgt[ maxn * 25 ] ;

  •  

  • node *pt = sgt ;

  •  

  • void build( int l , int r , ll a[] , node* &t ) {

  •     t = pt ++ ;

  •     t -> l = l , t -> r = r ;

  •     if ( l == r ) {

  •         t -> g = a[ l ] ; return ;

  •     }

  •     t -> mid = ( l + r ) >> 1 ;

  •     build( l , t -> mid , a , t -> lc ) , build( t -> mid + 1 , r , a , t -> rc ) ;

  •     t -> update(  ) ;

  • }

  •  

  • void change( int p , ll d , node *t ) {

  •     if ( t -> l == t -> r ) {

  •         t -> g += d ; return ;

  •     }

  •     change( p , d , p <= t -> mid ? t -> lc : t -> rc ) ;

  •     t -> update(  ) ;

  • }

  •  

  • ll query( int l , int r , node *t ) {

  •     if ( l > r ) return 0 ;

  •     if ( l == t -> l && r == t -> r ) return abs( t -> g ) ;

  •     if ( r <= t -> mid ) return query( l , r , t -> lc ) ;

  •     if ( l > t -> mid ) return query( l , r , t -> rc ) ;

  •     return gcd( query( l , t -> mid , t -> lc ) , query( t -> mid + 1 , r , t -> rc ) ) ;

  • }

  •  

  • struct Node {

  •      

  •     int l , r , mid ;

  •     node *t ;

  •     Node *lc , *rc ;

  •      

  •     inline void Update( int p ) {

  •         node *l = lc -> t , *r = rc -> t , *m = t ;

  •         for ( ; ; ) {

  •             m -> g = gcd( abs( l -> g ) , abs( r -> g ) ) ;

  •             if ( m -> l == m -> r ) break ;

  •             if ( p <= m -> mid ) {

  •                 l = l -> lc , r = r -> lc , m = m -> lc ;

  •             } else {

  •                 l = l -> rc , r = r -> rc , m = m -> rc ;

  •             }

  •         }

  •     }

  •      

  • } Sgt[ maxn << 2 ] ;

  •  

  • Node *Root , *Pt = Sgt ;

  •  

  • ll a[ maxn ] , del[ maxn ] , b[ maxn ] ;

  • int n , m , q , px , py ;

  •  

  • #define chose( x , y ) ( ( ( ( x - 1 ) * m + y ) > 0 && ( ( x - 1 ) * m + y ) <= ( n * m ) ) ? ( ( x - 1 ) * m + y ) : 0 )

  •  

  • void Merge( node *l , node *r , node* &t ) {

  •     t = pt ++ ;

  •     t -> l = l -> l , t -> r = l -> r , t -> mid = l -> mid , t -> g = gcd( l -> g , r -> g ) ;

  •     if ( t -> l == t -> r ) return ;

  •     Merge( l -> lc , r -> lc , t -> lc ) , Merge( l -> rc , r -> rc , t -> rc ) ;

  • }

  •  

  • void Build( int l , int r , Node* &t ) {

  •     t = Pt ++ ;

  •     t -> l = l , t -> r = r ;

  •     if ( l == r ) {

  •         rep( i , m ) b[ i ] = del[ chose( l , i ) ] ;

  •         build( 1 , m , b , t -> t ) ;

  •         return ;

  •     }

  •     t -> mid = ( l + r ) >> 1 ;

  •     Build( l , t -> mid , t -> lc ) , Build( t -> mid + 1 , r , t -> rc ) ;

  •     Merge( t -> lc -> t , t -> rc -> t , t -> t ) ;

  • }

  •  

  • void Change( int x , int y , ll d , Node *t ) {

  •     if ( t -> l == t -> r ) {

  •         change( y , d , t -> t ) ; return ;

  •     }

  •     Change( x , y , d , x <= t -> mid ? t -> lc : t -> rc ) ;

  •     t -> Update( y ) ;

  • }

  •  

  • ll Query( int l , int r , int x , int y , Node *t ) {

  •     if ( l > r ) return 0 ;

  •     if ( t -> l == l && t -> r == r ) return query( x , y , t -> t ) ;

  •     if ( r <= t -> mid ) return Query( l , r , x , y , t -> lc ) ;

  •     if ( l > t -> mid ) return Query( l , r , x , y , t -> rc ) ;

  •     return gcd( Query( l , t -> mid , x , y , t -> lc ) , Query( t -> mid + 1 , r , x , y , t -> rc ) ) ;

  • }

  •  

  • node *root[ 2 ] ;

  • ll num ;

  •  

  • int cnt = 0 ;

  •  

  • inline ll solve( int l , int r , int x , int y ) {

  •     ll ans = abs( num ) ;

  •     ans = gcd( ans , Query( l + 1 , r , x + 1 , y , Root ) ) ;

  •     ans = gcd( ans , query( x + 1 , y , root[ 0 ] ) ) ;

  •     ans = gcd( ans , query( l + 1 , r , root[ 1 ] ) ) ;

  •     return ans ;

  • }

  •  

  • inline void modify( int l , int r , int x , int y , ll d ) {

  •     if ( r + 1 <= n ) {

  •         if ( y + 1 <= m ) Change( r + 1 , y + 1 , d , Root ) ;

  •         Change( r + 1 , x , -d , Root ) ;

  •     }

  •     if ( y + 1 <= m ) Change( l , y + 1 , -d , Root ) ;

  •     Change( l , x , d , Root ) ;

  •     if ( l <= px && r >= px ) {

  •         change( x , d , root[ 0 ] ) ;

  •         if ( y + 1 <= m ) change( y + 1 , -d , root[ 0 ] ) ;

  •         if ( x <= py && y >= py ) num += d ;

  •     }

  •     if ( x <= py && y >= py ) {

  •         change( l , d , root[ 1 ] ) ;

  •         if ( r + 1 <= n ) change( r + 1 , -d , root[ 1 ] ) ;

  •     }

  • }

  •  

  • int main(  ) {

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

  •     memset( del , 0 , sizeof( del ) ) , memset( a , 0 , sizeof( a ) ) ;

  •     rep( i , n ) rep( j , m ) scanf( "%lld" , &a[ chose( i , j ) ] ) ;

  •     rep( i , n ) rep( j , m ) {

  •         del[ chose( i , j ) ] = a[ chose( i , j ) ] - a[ chose( i - 1 , j ) ] - a[ chose( i , j - 1 ) ] + a[ chose( i - 1 , j - 1 ) ] ;

  •     }

  •     Build( 1 , n , Root ) ;

  •     rep( i , m ) b[ i ] = a[ chose( px , i ) ] - a[ chose( px , i - 1 ) ] ;

  •     build( 1 , m , b , root[ 0 ] ) ;

  •     rep( i , n ) b[ i ] = a[ chose( i , py ) ] - a[ chose( i - 1 , py ) ] ;

  •     build( 1 , n , b , root[ 1 ] ) ;

  •     int x , y , z , l , r ; ll d ;

  •     num = a[ chose( px , py ) ] ;

  •     while ( q -- ) {

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

  •         if ( ! z ) {

  •             scanf( "%d%d%d%d" , &l , &x , &r , &y ) ;

  •             printf( "%lld\n" , solve( px - l , px + r , py - x , py + y ) ) ;

  •         } else {

  •             scanf( "%d%d%d%d%lld" , &l , &x , &r , &y , &d ) ;

  •             modify( l , r , x , y , d ) ;

  •         }

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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