柒葉灬 的博客

柒葉灬 的博客

「NOI2012」魔幻棋盘

posted on 2018-12-28 08:36:22 | under 赛后题解 |

一篇题解


看到这题,(这是什么鬼题!!!区间相减??还要维护 $gcd$ ???)就知道我是不可能在考场上写出来的,因为我甚至连最基本的二维线段树都不会。

前置技能:二维线段树,动态开点线段树

$n=1$ 的 $ 40 $ % 的情况时,给出结论:

$$ gcd(a_1,a_2,a_3,a_4)=gcd(a_1,a_2-a_1,a_3-a_2,a_4-a_3) $$

所以我们只要知道其中的一个 $a_1$ 就行了,因为每次询问一定会有给出的位置 $x \ ,\ y$ ,所以 $y$ 左边的数变为 $a_{x}-a_{x+1}$ ,右边的则是 $a_{x}-a_{x-1}$ 。

这样的好处是什么,这样子修改的时候就可以发现不是区间修改而是单点修改了


转到 $100$ 分的情况,我们可以先横着减一下变成:

$$ \begin{bmatrix} (a_{1,1}-a_{1,2})&(a_{1,2}-a_{1,3})&a_{1,3} \\(a_{2,1}-a_{2,2})&(a_{2,2}-a_{2,3})&a_{2,3}\\(a_{3,1}-a_{3,2})&(a_{3,2}-a_{3,3})&a_{3,3}\end{bmatrix}$$

竖着再减一波:

$$\begin{bmatrix} (a_{1,1}-a_{1,2}-a_{2,1}+a_{2,2} )&(a_{1,2}-a_{1,3}-a_{2,2}+a_{2,3})&(a_{1,3}-a_{2,3})\\(a_{2,1}-a_{2,2}-a_{3,1}+a_{3,2} )&(a_{2,2}-a_{2,3}-a_{3,2}+a_{3,3})&(a_{2,3}-a_{3,3})\\(a_{3,1}-a_{3,2})&(a_{3,2}-a_{3,3})&a_{3,3}\end{bmatrix}$$

得到了式子(只是左上角),发现这样子如果区间修改的话,实际上只是改 $4$ 个地方的值即可,然后按规律找到 $8$ 个不同地区的式子,分类讨论就行了。


#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
int n,m,x,y,q;
long long gcd(long long a,long long b){
    return !b?a:gcd(b,a%b);
}
struct P20{
    static const int maxn=105;
    long long mp[maxn][maxn];
    void solve(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lld",&mp[i][j]);
        while(q--){
            int opt,x1,y1,x2,y2;
            scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
            if(opt==0){
                x1=max(1,x-x1);
                x2=min(n,x+x2);
                y1=max(1,y-y1);
                y2=min(m,y+y2);
                long long ans=mp[x1][y1];
                for(int i=x1;i<=x2;i++)
                    for(int j=y1;j<=y2;j++){
                        ans=gcd(ans,mp[i][j]);
                    }
                printf("%lld\n",ans);
            }else {
                long long c;
                scanf("%lld",&c);
                for(int i=x1;i<=x2;i++)
                    for(int j=y1;j<=y2;j++)
                        mp[i][j]+=c;
            }
        }
    }
}p20;
struct P60{
    static const int maxn=5e5+5;
    long long A[maxn];
    struct node{
        int l,r;
        long long val;
    }tree[maxn<<2];
    void up(int p){
        tree[p].val=gcd(abs(tree[p<<1].val),abs(tree[p<<1|1].val));
    }
    void build(int l,int r,int p){
        tree[p].l=l;
        tree[p].r=r;
        if(l==r)return (void)(tree[p].val=A[l]);
        int mid=l+r>>1;
        build(l,mid,p<<1);
        build(mid+1,r,p<<1|1);
        up(p);
    }
    void update(int x,long long pos,int p){
        if(tree[p].l==tree[p].r)
            return (void)(tree[p].val+=pos);
        int mid=tree[p].l+tree[p].r>>1;
        if(x<=mid)update(x,pos,p<<1);
        else update(x,pos,p<<1|1);
        up(p);
    }
    long long Query(int l,int r,int p){
        if(tree[p].l==l&&tree[p].r==r){
            return abs(tree[p].val);
        }
        int mid=tree[p].l+tree[p].r>>1;
        if(r<=mid)return Query(l,r,p<<1);
        else if(l>mid)return Query(l,r,p<<1|1);
        else return gcd(Query(l,mid,p<<1),Query(mid+1,r,p<<1|1));
    }
    void solve(){
        for(int i=1;i<=m;i++)
            scanf("%lld",&A[i]);
        for(int i=1;i<y;i++)
            A[i]-=A[i+1];
        for(int i=m;i>y;i--)
            A[i]-=A[i-1];
        build(1,m,1);
        while(q--){
            int opt,x1,y1,x2,y2;
            scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
            if(opt==0){
                y1=max(1,y-y1);
                y2=min(m,y+y2);
                long long ans=Query(y1,y2,1);
                printf("%lld\n",ans);
            }else {
                long long c;
                scanf("%lld",&c);
                if(y1<=y&&y<=y2)update(y,c,1);

                if(y1<=y&&y1>1)update(y1-1,-c,1);
                else if(y1>y)update(y1,c,1);

                if(y2>=y&&y2<m)update(y2+1,-c,1);
                else if(y2<y)update(y2,c,1);
            }
        }
    }
}p60;
struct P100{
    static const int maxn=5e5+5;
    #define A(i,j) mp[(i-1)*m+j]
    struct SegTree{
        long long mp[maxn];
        int Rt,tot,son[maxn<<4][4];
        struct node{
            int x1,y1,x2,y2;
            long long val;
        }tree[maxn<<4];
        void up(int rt){
            tree[rt].val=gcd(gcd(abs(tree[son[rt][0]].val),abs(tree[son[rt][1]].val)),gcd(abs(tree[son[rt][2]].val),abs(tree[son[rt][3]].val)));
        }
        void build(int &rt,int x1,int y1,int x2,int y2){
            if(x1>x2||y1>y2)return;
            rt=++tot;
            tree[rt]=(node){x1,y1,x2,y2,0};
            if(x1==x2&&y1==y2){
                long long pos;
                int X=x1,Y=y1;
                if(X<x){
                    if(Y<y)pos=A(X,Y)-A(X+1,Y)-A(X,Y+1)+A(X+1,Y+1);
                    else if(Y>y)pos=A(X,Y)-A(X+1,Y)-A(X,Y-1)+A(X+1,Y-1);
                    else pos=A(X,Y)-A(X+1,Y);
                }else if(X>x){
                    if(Y<y)pos=A(X,Y)-A(X-1,Y)-A(X,Y+1)+A(X-1,Y+1);
                    else if(Y>y)pos=A(X,Y)-A(X-1,Y)-A(X,Y-1)+A(X-1,Y-1);
                    else pos=A(X,Y)-A(X-1,Y);
                }else {
                    if(Y<y)pos=A(X,Y)-A(X,Y+1);
                    else if(Y>y)pos=A(X,Y)-A(X,Y-1);
                    else pos=A(X,Y);
                }
                return (void)(tree[rt].val=pos);
            }
            int mx=x1+x2>>1,my=y1+y2>>1;
            build(son[rt][0],x1,y1,mx,my);
            build(son[rt][1],x1,my+1,mx,y2);
            build(son[rt][2],mx+1,y1,x2,my);
            build(son[rt][3],mx+1,my+1,x2,y2);
            up(rt);
        }
        void update(int x,int y,long long pos,int rt){
            if(tree[rt].x1==tree[rt].x2&&tree[rt].y1==tree[rt].y2)
                return (void)(tree[rt].val+=pos);
            int mx=tree[rt].x1+tree[rt].x2>>1;
            int my=tree[rt].y1+tree[rt].y2>>1;
            if(x<=mx){
                if(y<=my)update(x,y,pos,son[rt][0]);
                else update(x,y,pos,son[rt][1]);
            }else {
                if(y<=my)update(x,y,pos,son[rt][2]);
                else update(x,y,pos,son[rt][3]);
            }
            up(rt);
        }
        long long Query(int x1,int y1,int x2,int y2,int rt){
            if(tree[rt].x1==0)return 0;
            if(tree[rt].x1>=x1&&tree[rt].x2<=x2&&tree[rt].y1>=y1&&tree[rt].y2<=y2){
                return abs(tree[rt].val);
            }
            int mx=tree[rt].x1+tree[rt].x2>>1;
            int my=tree[rt].y1+tree[rt].y2>>1;
            long long ans=0;
            if(x1<=mx&&y1<=my)ans=gcd(Query(x1,y1,x2,y2,son[rt][0]),ans);
            if(x1<=mx&&y2>my)ans=gcd(Query(x1,y1,x2,y2,son[rt][1]),ans);
            if(x2>mx&&y1<=my)ans=gcd(Query(x1,y1,x2,y2,son[rt][2]),ans);
            if(x2>mx&&y2>my)ans=gcd(Query(x1,y1,x2,y2,son[rt][3]),ans);
            return ans;
        }
        void upd(int x,int y,long long pos){
            if(x<1||y<1||x>n||y>m)return;
            update(x,y,pos,1);
        }
    }S;
    void update(int x1,int y1,int x2,int y2,long long c){
        if(x2<x){
            if(y2<y){
                S.upd(x1-1,y1-1,c);
                S.upd(x2,y1-1,-c);
                S.upd(x1-1,y2,-c);
                S.upd(x2,y2,c);
            }else if(y1>y){
                S.upd(x1-1,y2+1,c);
                S.upd(x1-1,y1,-c);
                S.upd(x2,y2+1,-c);
                S.upd(x2,y1,c);
            }else {
                S.upd(x1-1,y1-1,c);
                S.upd(x2,y1-1,-c);
                S.upd(x1-1,y2+1,c);
                S.upd(x2,y2+1,-c);
                S.upd(x1-1,y,-c);
                S.upd(x2,y,c);
            }
        }else if(x1>x){
            if(y2<y){
                S.upd(x2+1,y1-1,c);
                S.upd(x1,y1-1,-c);
                S.upd(x2+1,y2,-c);
                S.upd(x1,y2,c);
            }else if(y1>y){
                S.upd(x2+1,y2+1,c);
                S.upd(x2+1,y1,-c);
                S.upd(x1,y2+1,-c);
                S.upd(x1,y1,c);
            }else {
                S.upd(x2+1,y1-1,c);
                S.upd(x1,y1-1,-c);
                S.upd(x2+1,y2+1,c);
                S.upd(x1,y2+1,-c);
                S.upd(x1,y,c);
                S.upd(x2+1,y,-c);
            }
        }else {
            if(y2<y){
                S.upd(x1-1,y1-1,c);
                S.upd(x1-1,y2,-c);
                S.upd(x2+1,y1-1,c);
                S.upd(x2+1,y2,-c);
                S.upd(x,y1-1,-c);
                S.upd(x,y2,c);
            }else if(y1>y){
                S.upd(x1-1,y2+1,c);
                S.upd(x1-1,y1,-c);
                S.upd(x2+1,y2+1,c);
                S.upd(x2+1,y1,-c);
                S.upd(x,y1,c);
                S.upd(x,y2+1,-c);
            }else {
                S.upd(x1-1,y1-1,c);
                S.upd(x1-1,y2+1,c);
                S.upd(x2+1,y1-1,c);
                S.upd(x2+1,y2+1,c);
                S.upd(x,y,c);
                S.upd(x,y1-1,-c);
                S.upd(x,y2+1,-c);
                S.upd(x1-1,y,-c);
                S.upd(x2+1,y,-c);
            }
        }
    }
    void solve(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lld",&S.A(i,j));
        S.build(S.Rt,1,1,n,m);
        int opt,x1,y1,x2,y2;
        while(q--){
            scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
            if(opt==1){
                long long c;
                scanf("%lld",&c);
                update(x1,y1,x2,y2,c);
            }else {
                x1=x-x1;y1=y-y1;
                x2=x+x2;y2=y+y2;
                printf("%lld\n",S.Query(x1,y1,x2,y2,1));
            }
        }
    }
}p100;
int main(){
//  freopen("data.in","r",stdin);
//  freopen("data.out","w",stdout);
    cin>>n>>m>>x>>y>>q;
    if(n<=100&&m<=100)p20.solve();
    else if(n==1)p60.solve();
    else p100.solve();
    return 0;
}

题外话,注意是动态开点,如果是四叉树则会开成 $max(n,m) * max(n,m)$ 矩阵的线段树了。