【题解】[NOI2012] 魔幻棋盘 二维线段树+差分 luoguP2086/bzoj2788 —Qiuly

于由Qiuly发布

细节诸多…………

$gcd$ 显然可以用线段树维护，但是如果是区间修改的话就不好办了。这个时候我们需要将原矩阵以棋盘守护者的位置为中心进行差分，那么区间修改就变为单点修改了，$gcd$ 自然好维护多了。

但是当我们整体加的时候，因为我们对原矩阵进行了拆分，所以对于每个点是加是减还是不动的话需要分类讨论一番。

经过观察我们会发现，有三种情况 (棋盘守护者的位置为 $(X,Y)$ )

  • 询问矩阵不包括 $(X,Y)$
    • 询问矩阵包含棋盘守护者所在的 $X$ 轴或是 $Y$ 轴。
    • 询问矩阵不包含棋盘守护者所在的 $X$ 轴或是 $Y$ 轴。
  • 询问矩阵包括 $(X,Y)$

这个时候我们可以自己更改原矩阵，然后输出其差分矩阵寻找规律了。需要注意的是判断的时候的边界情况以及自己修改的点的位置是否正确。细节很多，需要注意。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define F(i,x,y) for((i)=(x);(i)<=(y);++(i))
#define R(i,x,y) for((i)=(x);(i)>=(y);--(i))

const int N=5e5+7;
const int inf=1e9+9;

int n,m;LL a[N],b[N];
int id(int x,int y) {return (x-1)*m+y;}

namespace OI {
    LL abs(LL x) {return x>=0?x:-x;}
    LL gcd(LL x,LL y) {return y?gcd(y,x%y):abs(x);}
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace OI;

namespace _2D_Segment_tree {/*四分线段树*/
    #define midl ((x1+x2)>>1)
    #define midr ((y1+y2)>>1)
    int tot,root;
    struct Node {LL v;int ll,lr,rl,rr;}t[N<<4];
    void pushup(int x) {
        LL vl=gcd(t[t[x].ll].v,t[t[x].lr].v);
        LL vr=gcd(t[t[x].rl].v,t[t[x].rr].v);
        t[x].v=gcd(vl,vr);return;
    }
    void build(int&x,int x1,int y1,int x2,int y2) {
        if(x1>x2||y1>y2) return;x=++tot;
        if(x1==x2&&y1==y2) {t[x].v=a[id(x1,y1)];return;}
        build(t[x].ll,x1,y1,midl,midr);
        build(t[x].lr,midl+1,y1,x2,midr);
        build(t[x].rl,x1,midr+1,midl,y2);
        build(t[x].rr,midl+1,midr+1,x2,y2);
        pushup(x);return;
    }
    void change(int x,int x1,int y1,int x2,int y2,int X,int Y,LL val) {
        if(x1>X||X>x2||y1>Y||Y>y2) return;
        if(x1==x2&&y1==y2) {t[x].v+=val;return;}
        change(t[x].ll,x1,y1,midl,midr,X,Y,val);
        change(t[x].lr,midl+1,y1,x2,midr,X,Y,val);
        change(t[x].rl,x1,midr+1,midl,y2,X,Y,val);
        change(t[x].rr,midl+1,midr+1,x2,y2,X,Y,val);
        pushup(x);return;
    }
    LL query(int x,int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) {
        if(x1>X2||x2<X1||y1>Y2||y2<Y1) return 0;
        if(X1<=x1&&Y1<=y1&&x2<=X2&&y2<=Y2) return t[x].v;
        LL vll=query(t[x].ll,x1,y1,midl,midr,X1,Y1,X2,Y2);
        LL vlr=query(t[x].lr,midl+1,y1,x2,midr,X1,Y1,X2,Y2);
        LL vrl=query(t[x].rl,x1,midr+1,midl,y2,X1,Y1,X2,Y2);
        LL vrr=query(t[x].rr,midl+1,midr+1,x2,y2,X1,Y1,X2,Y2);
        return gcd(vll,gcd(vlr,gcd(vrl,vrr)));
    }
}using namespace _2D_Segment_tree;

int main() {
    IN(n),IN(m);
    int X,Y,T,i,j;IN(X),IN(Y),IN(T);
    for(int i=1;i<=n*m;++i) IN(a[i]);
    /*-------对原矩阵进行差分-------*/
    for(int i=1;i<=n*m;++i){
        if((i-1)%m+1<Y) b[i]=a[i]-a[i+1];
        else if((i-1)%m+1>Y) b[i]=a[i]-a[i-1];
        else b[i]=a[i];
    }
    for(int i=1;i<=n*m;++i) {
        if((i-1)/m+1<X) a[i]=b[i]-b[i+m];
        else if((i-1)/m+1>X) a[i]=b[i]-b[i-m];
        else a[i]=b[i];
    }
    /*----------------------------*/
    build(root,1,1,n,m);
    while(T--) {
        int op,x1,y1,x2,y2;IN(op),IN(x1),IN(y1),IN(x2),IN(y2);
        if(!op) printf("%lld\n",query(1,1,1,n,m,X-x1,Y-y1,X+x2,Y+y2));
        else {
            LL val;IN(val);
            if(x1<=X&&x2>=X&&y1<=Y&&y2>=Y) {/*包含了 (X,Y)*/
                change(1,1,1,n,m,X,Y,val);
                if(y1-1>=1) change(1,1,1,n,m,X,y1-1,-val);
                if(y2+1<=m) change(1,1,1,n,m,X,y2+1,-val);
                if(x1-1>=1) change(1,1,1,n,m,x1-1,Y,-val);
                if(x2+1<=n) change(1,1,1,n,m,x2+1,Y,-val);
                if(x1-1>=1&&y1-1>=1) change(1,1,1,n,m,x1-1,y1-1,val);
                if(x1-1>=1&&y2+1<=m) change(1,1,1,n,m,x1-1,y2+1,val);
                if(x2+1<=n&&y1-1>=1) change(1,1,1,n,m,x2+1,y1-1,val);
                if(x2+1<=n&&y2+1<=m) change(1,1,1,n,m,x2+1,y2+1,val);
            } else if(y1<=Y&&Y<=y2) {/*包含 Y 轴*/
                if(x1<X&&x2<X) {/*在上面*/
                    change(1,1,1,n,m,x2,Y,val);
                    if(y1-1>=1) change(1,1,1,n,m,x2,y1-1,-val);
                    if(y2+1<=m) change(1,1,1,n,m,x2,y2+1,-val);
                    if(x1-1>=1) change(1,1,1,n,m,x1-1,Y,-val);
                    if(x1-1>=1&&y1-1>=1) change(1,1,1,n,m,x1-1,y1-1,val);
                    if(x1-1>=1&&y2+1<=m) change(1,1,1,n,m,x1-1,y2+1,val);
                } else if(x1>X&&x2>X) {/*在下面*/
                    change(1,1,1,n,m,x1,Y,val);
                    if(y1-1>=1) change(1,1,1,n,m,x1,y1-1,-val);
                    if(y2+1<=m) change(1,1,1,n,m,x1,y2+1,-val);
                    if(x2+1<=n) change(1,1,1,n,m,x2+1,Y,-val);
                    if(x2+1<=n&&y1-1>=1) change(1,1,1,n,m,x2+1,y1-1,val);
                    if(x2+1<=n&&y2+1<=m) change(1,1,1,n,m,x2+1,y2+1,val);
                }
            } else if(x1<=X&&X<=x2) {/*包含 X 轴*/
                if(y1<Y&&y2<Y) {/*在左边*/
                    change(1,1,1,n,m,X,y2,val);
                    if(x1-1>=1) change(1,1,1,n,m,x1-1,y2,-val);
                    if(x2+1<=n) change(1,1,1,n,m,x2+1,y2,-val);
                    if(y1-1>=1) change(1,1,1,n,m,X,y1-1,-val);
                    if(y1-1>=1&&x1-1>=1) change(1,1,1,n,m,x1-1,y1-1,val);
                    if(y1-1>=1&&x2+1<=n) change(1,1,1,n,m,x2+1,y1-1,val);
                } else if(y1>Y&&y2>Y) {/*在右边*/
                    change(1,1,1,n,m,X,y1,val);
                    if(x1-1>=1) change(1,1,1,n,m,x1-1,y1,-val);
                    if(x2+1<=n) change(1,1,1,n,m,x2+1,y1,-val);
                    if(y2+1<=m) change(1,1,1,n,m,X,y2+1,-val);
                    if(y2+1<=m&&x1-1>=1) change(1,1,1,n,m,x1-1,y2+1,val);
                    if(y2+1<=m&&x2+1<=n) change(1,1,1,n,m,x2+1,y2+1,val);
                }
            } else {//剩下的判断四个角
                if(x2<X&&y2<Y) {//左上角
                    change(1,1,1,n,m,x2,y2,val);
                    if(y1-1>=1) change(1,1,1,n,m,x2,y1-1,-val);
                    if(x1-1>=1) change(1,1,1,n,m,x1-1,y2,-val);
                    if(x1-1>=1&&y1-1>=1) change(1,1,1,n,m,x1-1,y1-1,val);
                } else if(x2<X&&y1>Y) {/*右上角*/
                    change(1,1,1,n,m,x2,y1,val);
                    if(y2+1<=m) change(1,1,1,n,m,x2,y2+1,-val);
                    if(x1-1>=1) change(1,1,1,n,m,x1-1,y1,-val);
                    if(x1-1>=1&&y2+1<=m) change(1,1,1,n,m,x1-1,y2+1,val);
                } else if(x1>X&&y2<Y) {/*左下角*/
                    change(1,1,1,n,m,x1,y2,val);
                    if(y1-1>=1) change(1,1,1,n,m,x1,y1-1,-val);
                    if(x2+1<=n) change(1,1,1,n,m,x2+1,y2,-val);
                    if(x2+1<=n&&y1-1>=1) change(1,1,1,n,m,x2+1,y1-1,val);
                } else if(x1>X&&y1>Y) {/*右下角*/
                    change(1,1,1,n,m,x1,y1,val);
                    if(y2+1<=m) change(1,1,1,n,m,x1,y2+1,-val);
                    if(x2+1<=n) change(1,1,1,n,m,x2+1,y1,-val);
                    if(x2+1<=n&&y2+1<=m) change(1,1,1,n,m,x2+1,y2+1,val);
                }
            }
        }
    }
    return 0;
}
分类： 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注