bzoj 2877: [Noi2012]魔幻棋盘

.

题意：给出一个矩阵，每个操作可以使一个子矩阵加上一个数，或询问一个子矩阵的最大公约数。每个询问的中心都是(x,y)
题解：线段树。
相当于二维的bzoj 5028: 小Z的加油店，但加油店求的是一段的差分和第一个数的gcd，在这题就是矩阵的边界，我在这里卡了很久。。后来发现其实不一定要求第一个数，任意一个都是可以的。所以我们可以用一维线段树记录第x行和第y列的gcd，然后用二维线段树维护整个矩阵的gcd（都是差分后的）。
代码：
太恶心不想打
upd:
没忍住还是打了

#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;

int n,m,x,y;
struct tree1
{
    int l,r,lc,rc;
    long long c;
}tr1[1000010],tr2[1000010];
struct tree2
{
    int x1,y1,x2,y2,s1,s2,s3,s4;
    long long c;
}tr3[2000010];
int T,num1=0,num2=0,num3=0;
map<int,map<int,long long> >mp;
long long xy;

long long gcd(long long x,long long y)
{
    return y==0?x:gcd(y,x%y);
}
int bt1(tree1* tr,int& num,int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt1(tr,num,l,md);
        tr[i].rc=bt1(tr,num,md+1,r);
    }
    return i;
}
int bt2(int x1,int y1,int x2,int y2)
{
    int i=++num3;
    tr3[i].x1=x1;
    tr3[i].y1=y1;
    tr3[i].x2=x2;
    tr3[i].y2=y2;
    if(x1<x2&&y1<y2)
    {
        int md1=x1+x2>>1,md2=y1+y2>>1;
        tr3[i].s1=bt2(x1,y1,md1,md2);
        tr3[i].s2=bt2(x1,md2+1,md1,y2);
        tr3[i].s3=bt2(md1+1,y1,x2,md2);
        tr3[i].s4=bt2(md1+1,md2+1,x2,y2);
    }
    else if(x1<x2)
    {
        int md=x1+x2>>1;
        tr3[i].s1=bt2(x1,y1,md,y1);
        tr3[i].s3=bt2(md+1,y1,x2,y1);
    }
    else if(y1<y2)
    {
        int md=y1+y2>>1;
        tr3[i].s1=bt2(x1,y1,x1,md);
        tr3[i].s2=bt2(x1,md+1,x1,y2);
    }
    return i;
}
void chg1(tree1* tr,int i,long long c,int p)
{
    if(tr[i].l==tr[i].r)
    {
        tr[i].c+=c;
        return;
    }
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(p<=md)
    chg1(tr,lc,c,p);
    else
    chg1(tr,rc,c,p);
    tr[i].c=gcd(tr[lc].c,tr[rc].c);
}
void chg2(int i,int x,int y,long long c)
{
//    printf("%d %d %d\n",i,x,y);
    if(tr3[i].x1==tr3[i].x2&&tr3[i].y1==tr3[i].y2)
    {
        tr3[i].c+=c;
        return;
    }
    int md1=tr3[i].x1+tr3[i].x2>>1,md2=tr3[i].y1+tr3[i].y2>>1,s1=tr3[i].s1,s2=tr3[i].s2,s3=tr3[i].s3,s4=tr3[i].s4;
    if(x<=md1&&y<=md2)
    chg2(s1,x,y,c);
    else if(x<=md1&&y>md2)
    chg2(s2,x,y,c);
    else if(x>md1&&y<=md2)
    chg2(s3,x,y,c);
    else
    chg2(s4,x,y,c);
    tr3[i].c=gcd(gcd(tr3[s1].c,tr3[s2].c),gcd(tr3[s3].c,tr3[s4].c));
}
void chg(int x1,int y1,int x2,int y2,long long c)
{
    chg2(1,x1,y1,c);
    chg2(1,x2+1,y1,-c);
    chg2(1,x1,y2+1,-c);
    chg2(1,x2+1,y2+1,c);
    if(x1<=x&&x2>=x)
    {
        chg1(tr2,1,c,y1);
        chg1(tr2,1,-c,y2+1);
    }
    if(y1<=y&&y2>=y)
    {
        chg1(tr1,1,c,x1);
        chg1(tr1,1,-c,x2+1);
    }
    if(x1<=x&&x2>=x&&y1<=y&&y2>=y)
    xy+=c;
}
long long get1(tree1* tr,int i,int l,int r)
{
    if(l>r)
    return 0;
    if(tr[i].l==l&&tr[i].r==r)
    return tr[i].c;
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    return get1(tr,lc,l,r);
    else if(l>md)
    return get1(tr,rc,l,r);
    else
    return gcd(get1(tr,lc,l,md),get1(tr,rc,md+1,r));
}
long long get2(int i,int x1,int y1,int x2,int y2)
{
    if(x1>x2||y1>y2)
    return 0;
    if(tr3[i].x1==x1&&tr3[i].y1==y1&&tr3[i].x2==x2&&tr3[i].y2==y2)
    return tr3[i].c;
    int md1=tr3[i].x1+tr3[i].x2>>1,md2=tr3[i].y1+tr3[i].y2>>1,s1=tr3[i].s1,s2=tr3[i].s2,s3=tr3[i].s3,s4=tr3[i].s4;
    if(x2<=md1)
    {
        if(y2<=md2)
        {
            return get2(s1,x1,y1,x2,y2);
        }
        else if(y1>md2)
        {
            return get2(s2,x1,y1,x2,y2);
        }
        else
        {
            return gcd(get2(s1,x1,y1,x2,md2),get2(s2,x1,md2+1,x2,y2));
        }
    }
    else if(x1>md1)
    {
        if(y2<=md2)
        {
            return get2(s3,x1,y1,x2,y2);
        }
        else if(y1>md2)
        {
            return get2(s4,x1,y1,x2,y2);
        }
        else
        {
            return gcd(get2(s3,x1,y1,x2,md2),get2(s4,x1,md2+1,x2,y2));
        }
    }
    else
    {
        if(y2<=md2)
        {
            return gcd(get2(s1,x1,y1,md1,y2),get2(s3,md1+1,y1,x2,y2));
        }
        else if(y1>md2)
        {
            return gcd(get2(s2,x1,y1,md1,y2),get2(s4,md1+1,y1,x2,y2));
        }
        else
        {
            return gcd(gcd(get2(s1,x1,y1,md1,md2),get2(s2,x1,md2+1,md1,y2)),gcd(get2(s3,md1+1,y1,x2,md2),get2(s4,md1+1,md2+1,x2,y2)));
        }
    }
}
long long get(int x1,int y1,int x2,int y2)
{
    return gcd(xy,gcd(get1(tr1,1,x-x1+1,x+x2),gcd(get1(tr2,1,y-y1+1,y+y2),get2(1,x-x1+1,y-y1+1,x+x2,y+y2))));
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&x,&y,&T);
    bt1(tr1,num1,1,n+1);
    bt1(tr2,num2,1,m+1);
    bt2(1,1,n+1,m+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&mp[i][j]);
            chg(i,j,i,j,mp[i][j]);
        }
    }
    xy=mp[x][y];
    while(T--)
    {
        int op,x1,y1,x2,y2;
        scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
        if(op==0)
        printf("%lld\n",abs(get(x1,y1,x2,y2)));
        else
        {
            long long c;
            scanf("%lld",&c);
            chg(x1,y1,x2,y2,c);
        }/*
    for(int i=1;i<=num1;i++)
    printf("i:%d l:%d r:%d c:%lld\n",i,tr1[i].l,tr1[i].r,tr1[i].c);
    for(int i=1;i<=num2;i++)
    printf("i:%d l:%d r:%d c:%lld\n",i,tr2[i].l,tr2[i].r,tr2[i].c);
    for(int i=1;i<=num3;i++)
    printf("i:%d x1:%d y1:%d x2:%d y2:%d c:%lld\n",i,tr3[i].x1,tr3[i].y1,tr3[i].x2,tr3[i].y2,tr3[i].c);*/
    }
}

感谢sengxian的题解给我的启发。