题解

2 条题解

  • 0
    @ 2014-07-04 23:05:20

    #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 ;
    }

  • -1
    @ 2016-07-27 11:23:23

    测试数据 #0: Accepted, time = 156 ms, mem = 332448 KiB, score = 10

    测试数据 #1: Accepted, time = 281 ms, mem = 332448 KiB, score = 10

    测试数据 #2: Accepted, time = 578 ms, mem = 332448 KiB, score = 10

    测试数据 #3: Accepted, time = 734 ms, mem = 332444 KiB, score = 10

    测试数据 #4: Accepted, time = 750 ms, mem = 332448 KiB, score = 10

    测试数据 #5: Accepted, time = 890 ms, mem = 332448 KiB, score = 10

    测试数据 #6: Accepted, time = 1984 ms, mem = 332456 KiB, score = 10

    测试数据 #7: Accepted, time = 2546 ms, mem = 332448 KiB, score = 10

    测试数据 #8: Accepted, time = 1734 ms, mem = 332452 KiB, score = 10

    测试数据 #9: Accepted, time = 2843 ms, mem = 332452 KiB, score = 10

    Accepted, time = 12496 ms, mem = 332456 KiB, score = 100
    代码

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #define mid ((l+r)>>1)
    using namespace std;
    const int maxn=20000010;
    const int maxm=600010;
    int N,M,Q;
    struct Array{
    long long num[maxm];
    long long *operator {
    return &num[(x-1)*M];
    }
    }a,b;

    long long ABS(long long x){return x>0?x:-x;}
    long long GCD(long long x,long long y){
    return y?GCD(y,x%y):ABS(x);
    }

    int cnt,ch[maxn][2];
    long long w[maxn];

    void Merge(int &x,int p1,int p2,int l,int r){
    if(!x)x=++cnt;
    w[x]=GCD(w[p1],w[p2]);
    if(l!=r){
    Merge(ch[x][0],ch[p1][0],ch[p2][0],l,mid);
    Merge(ch[x][1],ch[p1][1],ch[p2][1],mid+1,r);
    }
    }

    void Build(int &x,int l,int r,long long t[]){
    x=++cnt;
    if(l==r){
    w[x]=t[l];
    return;
    }
    Build(ch[x][0],l,mid,t);
    Build(ch[x][1],mid+1,r,t);
    w[x]=GCD(w[ch[x][0]],w[ch[x][1]]);
    }

    int rt[maxm<<2];
    void Build(int x,int l,int r){
    if(l==r){
    Build(rt[x],1,M,a[l]);
    return;
    }
    Build(x<<1,l,mid);
    Build(x<<1|1,mid+1,r);
    Merge(rt[x],rt[x<<1],rt[x<<1|1],1,M);
    }

    int x,y,tx,ty;
    int tp,x1,y1,x2,y2;
    long long d;

    void Change(int x,int l,int r,long long d){
    if(l==r){w[x]+=d;return;}
    if(mid>=ty)Change(ch[x][0],l,mid,d);
    else Change(ch[x][1],mid+1,r,d);
    w[x]=GCD(w[ch[x][0]],w[ch[x][1]]);
    }

    void Update(int x,int p1,int p2,int l,int r){
    w[x]=GCD(w[p1],w[p2]);
    if(l==r)return;
    if(mid>=ty)Update(ch[x][0],ch[p1][0],ch[p2][0],l,mid);
    else Update(ch[x][1],ch[p1][1],ch[p2][1],mid+1,r);
    }

    void Modify(int x,int l,int r,long long d){
    if(l==r){
    Change(rt[x],1,M,d);
    return;
    }
    if(mid>=tx)Modify(x<<1,l,mid,d);
    else Modify(x<<1|1,mid+1,r,d);
    Update(rt[x],rt[x<<1],rt[x<<1|1],1,M);
    }

    long long Que(int x,int l,int r){
    if(l>=y1&&r<=y2)
    return w[x];
    long long ret=0;
    if(mid>=y1)ret=Que(ch[x][0],l,mid);
    if(mid<y2)ret=GCD(ret,Que(ch[x][1],mid+1,r));
    return ret;

    }

    long long Query(int x,int l,int r){
    if(l>=x1&&r<=x2)
    return Que(rt[x],1,M);
    long long ret=0;
    if(mid>=x1)ret=Query(x<<1,l,mid);
    if(mid<x2)ret=GCD(ret,Query(x<<1|1,mid+1,r));
    return ret;
    }

    int main(){
    scanf("%d%d",&N,&M);
    scanf("%d%d",&x,&y);
    scanf("%d",&Q);
    for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++)
    scanf("%lld",&b[i][j]);
    for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++){
    a[i][j]=b[i][j];
    if(i<x)a[i][j]-=b[i+1][j];
    if(i>x)a[i][j]-=b[i-1][j];
    if(j<y)a[i][j]-=b[i][j+1];
    if(j>y)a[i][j]-=b[i][j-1];
    if(i!=x&&j!=y)a[i][j]+=b[i+(i<x?1:-1)][j+(j<y?1:-1)];
    }

    Build(1,1,N);
    while(Q--){
    scanf("%d",&tp);
    scanf("%d%d",&x1,&y1);
    scanf("%d%d",&x2,&y2);
    if(tp==0){
    x1=x-x1;x2=x+x2;
    y1=y-y1;y2=y+y2;
    printf("%lld\n",Query(1,1,N));
    }
    if(tp==1){
    scanf("%lld",&d);

    {
    if(x1<=x&&y1<=y){
    tx=x1-1;ty=y1-1;
    if(tx&&ty)Modify(1,1,N,d);
    }

    if(x1<=x&&y1>y){
    tx=x1-1;ty=y1;
    if(tx)Modify(1,1,N,-d);
    }

    if(x1>x&&y1<=y){
    tx=x1;ty=y1-1;
    if(ty)Modify(1,1,N,-d);
    }

    if(x1>x&&y1>y){
    tx=x1;ty=y1;
    Modify(1,1,N,d);
    }
    }

    {
    if(x1<=x&&y2<y){
    tx=x1-1;ty=y2;
    if(tx)Modify(1,1,N,-d);
    }

    if(x1<=x&&y2>=y){
    tx=x1-1;ty=y2+1;
    if(tx&&ty<=M)Modify(1,1,N,d);
    }

    if(x1>x&&y2<y){
    tx=x1;ty=y2;
    Modify(1,1,N,d);
    }

    if(x1>x&&y2>=y){
    tx=x1;ty=y2+1;
    if(ty<=M)Modify(1,1,N,-d);
    }
    }

    {
    if(x2<x&&y1<=y){
    tx=x2;ty=y1-1;
    if(ty)Modify(1,1,N,-d);
    }

    if(x2<x&&y1>y){
    tx=x2;ty=y1;
    Modify(1,1,N,d);
    }

    if(x2>=x&&y1<=y){
    tx=x2+1;ty=y1-1;
    if(tx<=N&&ty)Modify(1,1,N,d);
    }

    if(x2>=x&&y1>y){
    tx=x2+1;ty=y1;
    if(tx<=N)Modify(1,1,N,-d);
    }
    }

    {
    if(x2<x&&y2<y){
    tx=x2;ty=y2;
    Modify(1,1,N,d);
    }

    if(x2<x&&y2>=y){
    tx=x2;ty=y2+1;
    if(ty<=M)Modify(1,1,N,-d);
    }

    if(x2>=x&&y2<y){
    tx=x2+1;ty=y2;
    if(tx<=N)Modify(1,1,N,-d);
    }

    if(x2>=x&&y2>=y){
    tx=x2+1;ty=y2+1;
    if(tx<=N&&ty<=M)Modify(1,1,N,d);
    }
    }

    if(x1<=x&&x2>=x){
    if(y1<=y){
    tx=x;ty=y1-1;
    if(ty)Modify(1,1,N,-d);
    }
    if(y1>y){
    tx=x;ty=y1;
    Modify(1,1,N,d);
    }

    if(y2<y){
    tx=x;ty=y2;
    Modify(1,1,N,d);
    }
    if(y2>=y){
    tx=x;ty=y2+1;
    if(ty<=M)Modify(1,1,N,-d);
    }
    }

    if(y1<=y&&y2>=y){
    if(x1<=x){
    tx=x1-1;ty=y;
    if(tx)Modify(1,1,N,-d);
    }
    if(x1>x){
    tx=x1;ty=y;
    Modify(1,1,N,d);
    }

    if(x2<x){
    tx=x2;ty=y;
    Modify(1,1,N,d);
    }
    if(x2>=x){
    tx=x2+1;ty=y;
    if(tx<=N)Modify(1,1,N,-d);
    }
    }

    if(x1<=x&&x2>=x&&y1<=y&&y2>=y){
    tx=x;ty=y;
    Modify(1,1,N,d);
    }
    }
    }

    return 0;
    }

  • 1

信息

ID
1806
难度
7
分类
(无)
标签
递交数
125
已通过
20
通过率
16%
被复制
2
上传者