BZOJ2877：[NOI2012]魔幻棋盘

浅谈树状数组与主席树：https://www.cnblogs.com/AKMer/p/9946944.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2877

这就是个屎题。

而且至今我还不知道为什么洛谷和本地都可以过但是\(BZOJ\)会\(RE\)

因此我觉得我遇到了学术上的难题。

利用更相减损数以棋盘守护者为中心进行二维差分，那么每次修改就变成若干个点的值的修改了。

然后二维线段树维护差分值。

详细一点你们可以看这位大佬的博客（我是懒得搞了）：http://www.cnblogs.com/milky-w/p/8530723.html

这篇博客存在的意义就是为了给某些不喜欢指针的朋友们提供一份好看点的不能在BZOJ过但是正确性没有问题的代码的……

反正我是不想再来回头看这题了，简直屎得一批。

时间复杂度：\(O(nmlognlogm)\)

空间复杂度：\(O(mn)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=5e5+5;

int n,m,X,Y,T;
ll a[maxn],b[maxn];

ll read() {
    ll x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

ll gcd(ll a,ll b) {
    if(!b)return abs(a);
    return gcd(b,a%b);
}

struct segment_tree_y {
    int tot;
    ll val[maxn<<2];
    int ls[maxn<<2],rs[maxn<<2];

    void build(int &p,int l,int r,int x) {
        p=++tot;
        if(l==r) {val[p]=a[(x-1)*m+l];return;}
        int mid=(l+r)>>1;
        build(ls[p],l,mid,x);
        build(rs[p],mid+1,r,x);
        val[p]=gcd(val[ls[p]],val[rs[p]]);
    }

    void update(int &p1,int p2,int p3,int l,int r) {
        p1=++tot;
        if(l==r) {val[p1]=gcd(val[p2],val[p3]);return;}
        int mid=(l+r)>>1;
        update(ls[p1],ls[p2],ls[p3],l,mid);
        update(rs[p1],rs[p2],rs[p3],mid+1,r);
        val[p1]=gcd(val[ls[p1]],val[rs[p1]]);
    }

    ll query(int p,int l,int r,int L,int R) {
        if(L<=l&&r<=R)return val[p];
        int mid=(l+r)>>1;ll res=0;
        if(L<=mid)res=query(ls[p],l,mid,L,R);
        if(R>mid)res=gcd(res,query(rs[p],mid+1,r,L,R));
        return res;
    }

    void add(int p,int l,int r,int pos,ll v) {
        if(l==r) {val[p]+=v;return;}
        int mid=(l+r)>>1;
        if(pos<=mid)add(ls[p],l,mid,pos,v);
        else add(rs[p],mid+1,r,pos,v);
        val[p]=gcd(val[ls[p]],val[rs[p]]);
    }

    void change(int p,int l,int r,int pos,ll v) {
        if(l==r) {val[p]=v;return;}
        int mid=(l+r)>>1;
        if(pos<=mid)change(ls[p],l,mid,pos,v);
        else change(rs[p],mid+1,r,pos,v);
        val[p]=gcd(val[ls[p]],val[rs[p]]);
    }
}T2;

struct segment_tree_x {
    int rt[maxn<<2];

    void build(int p,int l,int r) {
        if(l==r) {T2.build(rt[p],1,m,l);return;}
        int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        T2.update(rt[p],rt[p<<1],rt[p<<1|1],1,m);
    }

    ll query(int p,int l,int r,int x1,int x2,int y1,int y2) {
        if(x1<=l&&r<=x2)return T2.query(rt[p],1,m,y1,y2);
        int mid=(l+r)>>1;ll res=0;
        if(x1<=mid)res=query(p<<1,l,mid,x1,x2,y1,y2);
        if(x2>mid)res=gcd(res,query(p<<1|1,mid+1,r,x1,x2,y1,y2));
        return res;
    }

    void add(int p,int l,int r,int x,int y,ll v) {
        if(x<1||x>n||y<1||y>m)return;
        if(l==r) {T2.add(rt[p],1,m,y,v);return;}
        int mid=(l+r)>>1;
        if(x<=mid)add(p<<1,l,mid,x,y,v);
        else add(p<<1|1,mid+1,r,x,y,v);
        ll lv=T2.query(rt[p<<1],1,m,y,y);
        ll rv=T2.query(rt[p<<1|1],1,m,y,y);
        T2.change(rt[p],1,m,y,gcd(lv,rv));
    }
}T1;

int main() {
    n=read(),m=read(),X=read(),Y=read(),T=read();
    for(int i=1;i<=n*m;i++)a[i]=read();
    for(int i=1;i<=n*m;i++) {
        int pos=(i-1)%m+1;
        if(pos<Y)b[i]=a[i]-a[i+1];
        else if(pos>Y)b[i]=a[i]-a[i-1];
        else b[i]=a[i];
    }
    for(int i=1;i<=n*m;i++) {
        int pos=(i-1)/m+1;
        if(pos<X)a[i]=b[i]-b[i+m];
        else if(pos>X)a[i]=b[i]-b[i-m];
        else a[i]=b[i];
    }
    T1.build(1,1,n);
    while(T--) {
        int opt=read(),x1=read(),y1=read(),x2=read(),y2=read();
        if(!opt) {
            x1=X-x1,x2=X+x2,y1=Y-y1,y2=Y+y2;
            printf("%lld\n",T1.query(1,1,n,x1,x2,y1,y2));
        }
        if(opt) {
            ll val=read();
            if(x1<=X&&x2>=X&&y1<=Y&&y2>=Y) {
                T1.add(1,1,n,X,Y,val);
                T1.add(1,1,n,x1-1,y1-1,val);
                T1.add(1,1,n,x1-1,y2+1,val);
                T1.add(1,1,n,x2+1,y1-1,val);
                T1.add(1,1,n,x2+1,y2+1,val);
                T1.add(1,1,n,x1-1,Y,-val);
                T1.add(1,1,n,x2+1,Y,-val);
                T1.add(1,1,n,X,y1-1,-val);
                T1.add(1,1,n,X,y2+1,-val);
            }
            else if(y1<=Y&&y2>=Y) {
                if(x1<X) {
                    T1.add(1,1,n,x2,Y,val);
                    T1.add(1,1,n,x1-1,y1-1,val);
                    T1.add(1,1,n,x1-1,y2+1,val);
                    T1.add(1,1,n,x1-1,Y,-val);
                    T1.add(1,1,n,x2,y1-1,-val);
                    T1.add(1,1,n,x2,y2+1,-val);
                }
                else {
                    T1.add(1,1,n,x1,Y,val);
                    T1.add(1,1,n,x2+1,y1-1,val);
                    T1.add(1,1,n,x2+1,y2+1,val);
                    T1.add(1,1,n,x2+1,Y,-val);
                    T1.add(1,1,n,x1,y1-1,-val);
                    T1.add(1,1,n,x1,y2+1,-val);
                }
            }
            else if(x1<=X&&x2>=X) {
                if(y1<Y) {
                    T1.add(1,1,n,X,y2,val);
                    T1.add(1,1,n,x1-1,y1-1,val);
                    T1.add(1,1,n,x2+1,y1-1,val);
                    T1.add(1,1,n,X,y1-1,-val);
                    T1.add(1,1,n,x1-1,y2,-val);
                    T1.add(1,1,n,x2+1,y2,-val);
                }
                else {
                    T1.add(1,1,n,X,y1,val);
                    T1.add(1,1,n,x1-1,y2+1,val);
                    T1.add(1,1,n,x2+1,y2+1,val);
                    T1.add(1,1,n,X,y2+1,-val);
                    T1.add(1,1,n,x1-1,y1,-val);
                    T1.add(1,1,n,x2+1,y1,-val);
                }
            }
            else if(x1<X&&y1<Y) {
                T1.add(1,1,n,x2,y2,val);
                T1.add(1,1,n,x1-1,y1-1,val);
                T1.add(1,1,n,x1-1,y2,-val);
                T1.add(1,1,n,x2,y1-1,-val);
            }
            else if(x1<X&&y1>Y) {
                T1.add(1,1,n,x2,y1,val);
                T1.add(1,1,n,x1-1,y2+1,val);
                T1.add(1,1,n,x1-1,y1,-val);
                T1.add(1,1,n,x2,y2+1,-val);
            }
            else if(x1>X&&y1<Y) {
                T1.add(1,1,n,x1,y2,val);
                T1.add(1,1,n,x2+1,y1-1,val);
                T1.add(1,1,n,x1,y1-1,-val);
                T1.add(1,1,n,x2+1,y2,-val);
            }
            else if(x1>X&&y1>Y) {
                T1.add(1,1,n,x1,y1,val);
                T1.add(1,1,n,x2+1,y2+1,val);
                T1.add(1,1,n,x1,y2+1,-val);
                T1.add(1,1,n,x2+1,y1,-val);
            }
        }
    }
    return 0;
}

BZOJ2877：[NOI2012]魔幻棋盘

原文：https://www.cnblogs.com/AKMer/p/10211209.html