题目

我的思路：

首先算出n*m,然后算出$\sqrt{nm}$

如果$\sqrt{nm}>=m$则转换矩阵：

1 2 3

4 5 6

7 8 9

10 11 12

转换成：

3 6 9 12

2 5 8 11

1 4 7 10

并交换n,m

然后用n个一维线段树维护GCD

这样复杂度就变成了$最好：O(Tlognm)最坏：O(T\sqrt{nm}log\sqrt{nm})$

Code:

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll tree[32000005],tree2[500005],a[500005],b[500005],c[500005];
ll n,m;
inline ll cxy(ll x,ll y){
    return (x-1)*m+y;
} 
inline ll cly(ll x,ll y){
    return (x-1)*(m<<2)+y;
}
inline ll read(){
    ll x(0),f(1);
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
inline ll exgcd(ll x,ll y){
    if(!y){
        return abs(x);    
    }
    return exgcd(y,x%y);
}
inline void psup(ll x,ll y){
    tree[cly(x,y)]=exgcd(tree[cly(x,y<<1)],tree[cly(x,y<<1|1)]);
}
inline void build(ll now,ll x,ll l,ll r){
    if(l==r){
        tree[cly(x,now)]=b[cxy(x,l)];
        return ;
    }
    int mid((l+r)>>1);
    build(now<<1,x,l,mid);
    build(now<<1|1,x,mid+1,r);
    psup(x,now);
}
inline void add(ll p,ll x,ll l,ll r,ll pl,ll pr,ll v){
    if(l==r){
        tree[cly(x,p)]+=v;
        return ;
    }
    int mid((l+r)>>1);
    if(pl<=mid){
        add(p<<1,x,l,mid,pl,pr,v);
    }
    if(mid<pr){
        add(p<<1|1,x,mid+1,r,pl,pr,v);
    }
    psup(x,p);
}
inline ll query(ll p,ll x,ll l,ll r,ll pl,ll pr){
    if(l>r){
        return 0;
    }
    if(pl<=l&&r<=pr){
        return tree[cly(x,p)];
    }
    int mid((l+r)>>1);
    register ll ans(0);
    if(pl<=mid){
        ans=query(p<<1,x,l,mid,pl,pr);
    }
    if(mid<pr){
        ans=exgcd(ans,query(p<<1|1,x,mid+1,r,pl,pr));
    }
    return abs(ans);
}
inline ll lowbit(ll x){
    return x&-x;
}
inline void add_sz(ll x,ll y,ll k){
    ll opx(y);
    while(opx<=m){
        tree2[cxy(x,opx)]+=k;
        opx+=lowbit(opx);
    }
}
inline ll query_sz(ll x,ll y){
    register ll ans(0),opx(y);
    while(opx){
        ans+=tree2[cxy(x,opx)];
        opx-=lowbit(opx);
    }
    return abs(ans);
}
int main(){
    register ll x1,x2,y1,y2,rot,opt,cx,p,i,tx,ty;
    n=read();m=read();
	register ll x(read()),y(read()),t(read());
    for(register ll i(1);i<=n;++i){
        for(register ll j(1);j<=m;++j){
            a[cxy(i,j)]=read();
        }
    }
    rot=n*m;
    rot=ll(sqrt(rot));
    if(rot>=m){
        for(register ll i(1);i<=n;++i){
            for(register ll j(1);j<=m;++j){
                c[(m-j)*n+i]=a[cxy(i,j)];
            }
        }
        swap(n,m);
        for(register ll i(1);i<=n;++i){
            for(register ll j(1);j<=m;++j){
                if(j==1){
                    b[cxy(i,j)]=c[cxy(i,j)];
                    continue;
                }
                b[cxy(i,j)]=c[cxy(i,j)]-c[cxy(i,j-1)];
            }
        }
        for(int i(1);i<=n;++i){
            build(1,i,1,m);
        }
        for(int i(1);i<=n;++i){
            for(int j(1);j<=m;++j){
                add_sz(i,j,b[cxy(i,j)]);
            }
        }
        while(t--){
            opt=read();x1=read();y1=read();x2=read();y2=read();
            if(opt==0){
                x1=x-x1;
                x2=x+x2;
                y1=y-y1;
                y2=y+y2;
                p=y1;
                y1=x1;
                x1=n-p+1;
                p=y2;
                y2=x2;
                x2=n-p+1;
                tx=x1;ty=x2;
                x1=min(tx,ty);
                x2=max(tx,ty);
                tx=y1;ty=y2;
                y1=min(tx,ty);
                y2=max(tx,ty);
                register ll ans(0);
                for(i=x1;i<=x2-20;i+=20){
                    ans=exgcd(exgcd(query_sz(i+0,y1),ans),query(1,i+0,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+1,y1),ans),query(1,i+1,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+2,y1),ans),query(1,i+2,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+3,y1),ans),query(1,i+3,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+4,y1),ans),query(1,i+4,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+5,y1),ans),query(1,i+5,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+6,y1),ans),query(1,i+6,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+7,y1),ans),query(1,i+7,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+8,y1),ans),query(1,i+8,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+9,y1),ans),query(1,i+9,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+10,y1),ans),query(1,i+10,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+11,y1),ans),query(1,i+11,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+12,y1),ans),query(1,i+12,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+13,y1),ans),query(1,i+13,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+14,y1),ans),query(1,i+14,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+15,y1),ans),query(1,i+15,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+16,y1),ans),query(1,i+16,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+17,y1),ans),query(1,i+17,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+18,y1),ans),query(1,i+18,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+19,y1),ans),query(1,i+19,1,m,y1+1,y2));
                }
                if(!i){
                    i=x1;
                }
                while(i<=x2){
                    ans=exgcd(exgcd(query_sz(i,y1),ans),query(1,i,1,m,y1+1,y2));
                    ++i;
                }
                print(ans);
                printf("\n");
            }
            if(opt==1){
                cx=read();
                p=y1;
                y1=x1;
                x1=n-p+1;
                p=y2;
                y2=x2;
                x2=n-p+1;
                tx=x1;ty=x2;
                x1=min(tx,ty);
                x2=max(tx,ty);
                tx=y1;ty=y2;
                y1=min(tx,ty);
                y2=max(tx,ty);
                for(i=x1;i<=x2-20;i+=20){
                    add(1,i+0,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+0,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+0,y1,cx);
                    add_sz(i+0,y2+1,-cx);
                    add(1,i+1,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+1,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+1,y1,cx);
                    add_sz(i+1,y2+1,-cx);
                    add(1,i+2,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+2,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+2,y1,cx);
                    add_sz(i+2,y2+1,-cx);
                    add(1,i+3,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+3,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+3,y1,cx);
                    add_sz(i+3,y2+1,-cx);
                    add(1,i+4,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+4,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+4,y1,cx);
                    add_sz(i+4,y2+1,-cx);
                    add(1,i+5,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+5,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+5,y1,cx);
                    add_sz(i+5,y2+1,-cx);
                    add(1,i+6,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+6,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+6,y1,cx);
                    add_sz(i+6,y2+1,-cx);
                    add(1,i+7,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+7,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+7,y1,cx);
                    add_sz(i+7,y2+1,-cx);
                    add(1,i+8,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+8,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+8,y1,cx);
                    add_sz(i+8,y2+1,-cx);
                    add(1,i+9,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+9,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+9,y1,cx);
                    add_sz(i+9,y2+1,-cx);
                    add(1,i+10,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+10,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+10,y1,cx);
                    add_sz(i+10,y2+1,-cx);
                    add(1,i+11,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+11,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+11,y1,cx);
                    add_sz(i+11,y2+1,-cx);
                    add(1,i+12,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+12,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+12,y1,cx);
                    add_sz(i+12,y2+1,-cx);
                    add(1,i+13,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+13,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+13,y1,cx);
                    add_sz(i+13,y2+1,-cx);
                    add(1,i+14,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+14,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+14,y1,cx);
                    add_sz(i+14,y2+1,-cx);
                    add(1,i+15,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+15,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+15,y1,cx);
                    add_sz(i+15,y2+1,-cx);
                    add(1,i+16,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+16,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+16,y1,cx);
                    add_sz(i+16,y2+1,-cx);
                    add(1,i+17,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+17,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+17,y1,cx);
                    add_sz(i+17,y2+1,-cx);
                    add(1,i+18,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+18,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+18,y1,cx);
                    add_sz(i+18,y2+1,-cx);
                    add(1,i+19,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+19,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+19,y1,cx);
                    add_sz(i+19,y2+1,-cx);
                }
                if(!i){
                    i=x1;
                }
                while(i<=x2){
                    add(1,i,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i,y1,cx);
                    add_sz(i,y2+1,-cx);
                    ++i;
                }
            }
        }
        return 0; 
    }
    else{
        for(register ll i(1);i<=n;++i){
            for(register ll j(1);j<=m;++j){
                if(j==1){
                    b[cxy(i,j)]=a[cxy(i,j)];
                    continue;
                }
                b[cxy(i,j)]=a[cxy(i,j)]-a[cxy(i,j-1)];
            }
        }
        for(register ll i(1);i<=n;++i){
            build(1,i,1,m);
        }
        for(register ll i(1);i<=n;++i){
            for(register ll j(1);j<=m;++j){
                add_sz(i,j,b[cxy(i,j)]);
            }
        }
        while(t--){
            opt=read();x1=read();y1=read();x2=read();y2=read();
            if(opt==0){
                x1=x-x1;
                x2=x+x2;
                y1=y-y1;
                y2=y+y2;
                register ll ans(0);
                for(i=x1;i<=x2-20;i+=20){
                    ans=exgcd(exgcd(query_sz(i+0,y1),ans),query(1,i+0,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+1,y1),ans),query(1,i+1,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+2,y1),ans),query(1,i+2,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+3,y1),ans),query(1,i+3,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+4,y1),ans),query(1,i+4,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+5,y1),ans),query(1,i+5,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+6,y1),ans),query(1,i+6,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+7,y1),ans),query(1,i+7,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+8,y1),ans),query(1,i+8,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+9,y1),ans),query(1,i+9,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+10,y1),ans),query(1,i+10,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+11,y1),ans),query(1,i+11,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+12,y1),ans),query(1,i+12,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+13,y1),ans),query(1,i+13,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+14,y1),ans),query(1,i+14,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+15,y1),ans),query(1,i+15,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+16,y1),ans),query(1,i+16,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+17,y1),ans),query(1,i+17,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+18,y1),ans),query(1,i+18,1,m,y1+1,y2));
                    ans=exgcd(exgcd(query_sz(i+19,y1),ans),query(1,i+19,1,m,y1+1,y2));
                }
                while(i<=x2){
                    ans=exgcd(exgcd(query_sz(i,y1),ans),query(1,i,1,m,y1+1,y2));
                    ++i;
                }
                print(ans);
                printf("\n");
            }
            if(opt==1){
                cx=read();
                for(i=x1;i<=x2-20;i+=20){
                    add(1,i+0,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+0,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+0,y1,cx);
                    add_sz(i+0,y2+1,-cx);
                    add(1,i+1,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+1,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+1,y1,cx);
                    add_sz(i+1,y2+1,-cx);
                    add(1,i+2,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+2,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+2,y1,cx);
                    add_sz(i+2,y2+1,-cx);
                    add(1,i+3,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+3,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+3,y1,cx);
                    add_sz(i+3,y2+1,-cx);
                    add(1,i+4,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+4,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+4,y1,cx);
                    add_sz(i+4,y2+1,-cx);
                    add(1,i+5,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+5,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+5,y1,cx);
                    add_sz(i+5,y2+1,-cx);
                    add(1,i+6,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+6,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+6,y1,cx);
                    add_sz(i+6,y2+1,-cx);
                    add(1,i+7,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+7,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+7,y1,cx);
                    add_sz(i+7,y2+1,-cx);
                    add(1,i+8,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+8,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+8,y1,cx);
                    add_sz(i+8,y2+1,-cx);
                    add(1,i+9,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+9,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+9,y1,cx);
                    add_sz(i+9,y2+1,-cx);
                    add(1,i+10,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+10,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+10,y1,cx);
                    add_sz(i+10,y2+1,-cx);
                    add(1,i+11,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+11,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+11,y1,cx);
                    add_sz(i+11,y2+1,-cx);
                    add(1,i+12,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+12,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+12,y1,cx);
                    add_sz(i+12,y2+1,-cx);
                    add(1,i+13,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+13,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+13,y1,cx);
                    add_sz(i+13,y2+1,-cx);
                    add(1,i+14,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+14,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+14,y1,cx);
                    add_sz(i+14,y2+1,-cx);
                    add(1,i+15,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+15,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+15,y1,cx);
                    add_sz(i+15,y2+1,-cx);
                    add(1,i+16,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+16,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+16,y1,cx);
                    add_sz(i+16,y2+1,-cx);
                    add(1,i+17,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+17,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+17,y1,cx);
                    add_sz(i+17,y2+1,-cx);
                    add(1,i+18,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+18,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+18,y1,cx);
                    add_sz(i+18,y2+1,-cx);
                    add(1,i+19,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i+19,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i+19,y1,cx);
                    add_sz(i+19,y2+1,-cx);
                }
                while(i<=x2){
                    add(1,i,1,m,y1,y1,cx);
                    if(y2+1<=m){
                        add(1,i,1,m,y2+1,y2+1,-cx);
                    }
                    add_sz(i,y1,cx);
                    add_sz(i,y2+1,-cx);
                    ++i;
                }
            }
        }
    }
    return 0;
}

卡常卡了N年。。。