BZOJ-2877: [Noi2012]魔幻棋盘（线段树）

题目：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 ;

}