題目：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))玛追，所以對(duì)于矩陣[l,r,x,y]（表示矩陣四個(gè)頂點(diǎn)中税课，最小的行數(shù)為l闲延，最大為r，最小的列數(shù)為x韩玩，最大的為y）垒玲，設(shè)題目中的定點(diǎn)為(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 ) )
然后，用兩棵一維線段樹(shù)維護(hù)G( a( i , py ) - a( i - 1 , py ) ) ( l < i <= r ) , G( a( px , j ) - a( px , j - 1 ) ) ( x < j <= y ) ,用一棵二維線段樹(shù)維護(hù)G( a( i , j ) - a( i , j - 1 ) - a( i - 1 , j ) + a( i - 1 , j - 1 ) )( l < i <= r && x < j <= y ) 找颓，我們神奇的發(fā)現(xiàn)每次修改操作在這三棵線段樹(shù)上都是單點(diǎn)修改合愈，然后就可以AC了。
時(shí)間復(fù)雜度：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 ;
}
