P2086 [NOI2012] 魔幻棋盘

题目描述

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 $N$ 行 $M$ 列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列（行与列均从 $1$ 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

• （a）询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。
• （b）修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 $19930324$ 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 $100\%$ 的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的 $T$ 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62}-1$ 的正整数。

输入格式

第一行为两个正整数 $N,M$，表示棋盘的大小。

第二行为两个正整数 $X,Y$，表示棋盘守护者的位置。

第三行仅有一个正整数 $T$，表示棋盘守护者将进行 $T$ 次操作。

接下来 $N$ 行，每行有 $M$ 个正整数，用来描述初始时棋盘上每个位置的数。

接下来 $T$ 行，按操作的时间顺序给出 $T$ 次操作。每行描述一次操作，以一个数字 $0$ 或 $1$ 开头：

• 若以数字 $0$ 开头，表示此操作为询问，随后会有四个非负整数 $x_1,y_1,x_2,y_2$，表示询问的区域是以棋盘守护者的位置为基础向上扩展
  $x_1$ 行，向下扩展 $x_1$ 行，向左扩展 $y_1$ 列，向右扩展 $y_2$ 列得到的矩形区域（详见样例）。
• 若以数字 $1$ 开头，表示此操作为修改，随后会有四个正整数 $x_1,y_1,x_2,y_2$ 和一个整数 $c$，表示修改区域的上、下边界分别为第 $x_1,x_2$ 行，左、右边界分别为第 $y_1,y_2$ 列（详见样例），在此矩形区域内的所有数统一加上 $c$（注意 $c$ 可能为负数）。

输出格式

对于每次询问操作，每行输出一个数，表示该区域内所有数的最大公约数。

输入输出样例 #1

输入 #1

2 2
1 1
4
6 12
18 24
0 0 0 1 0
1 1 1 1 2 6
1 2 1 2 2 6
0 0 0 1 1

输出 #1

6
6

说明/提示

对于第一、第四次操作（查询操作）后，加粗部分表示查询区域。

对于第二、第三次操作（修改操作）后，加粗部分表示修改区域。

测试数据分为 A、B、C 三类：

A 类数据占 $20\%$，满足 $N\le 100$，$M\le 100$，$T\le 2\times 10^4$。

B 类数据占 $40\%$，满足 $N=1$，$M\le 5\times 10^5$，$T\le 10^5$。

C 类数据占 $40\%$，满足 $N\times M\le 5\times 10^5$，$T\le 10^5$。

在每类数据中，均有 $50\%$ 的数据满足每次修改操作仅含一个格子（即 $x_1=x_2$，$y_1=y_2$）。

输入数据保证满足题目描述中的所有性质。

答案

#include<bits/stdc++.h>
#define maxn 2000010
#define maxm 32000010
#define a(i,j) a[(i-1)*m+j]
#define b(i,j) b[(i-1)*m+j]
#define ls (cur<<1)
#define rs (cur<<1|1)
#define mid ((l+r)>>1)
#define midx ((u+d)>>1)
#define midy ((l+r)>>1)
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,m,sx,sy,q,root,rt=1,tree_cnt;
int uls[maxm],urs[maxm],dls[maxm],drs[maxm];
ll w;
ll a[maxn],b[maxn],val[maxm];
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):abs(a);
}
void build(int u,int d,int l,int r,int &cur)
{
    if(u>d||l>r) return;
    if(!cur) cur=++tree_cnt;
    if(u==d&&l==r)
    {
        val[cur]=b(u,l);
        return;
    }
    build(u,midx,l,midy,uls[cur]),build(u,midx,midy+1,r,urs[cur]);
    build(midx+1,d,l,midy,dls[cur]),build(midx+1,d,midy+1,r,drs[cur]);
    val[cur]=gcd(gcd(val[uls[cur]],val[urs[cur]]),gcd(val[dls[cur]],val[drs[cur]]));
}
void modify(int u,int d,int l,int r,int x,int y,ll v,int cur)
{
    if(l==r&&u==d)
    {
        val[cur]+=v;
        return;
    }
    if(x<=midx)
    {
        if(y<=midy) modify(u,midx,l,midy,x,y,v,uls[cur]);
        else modify(u,midx,mid+1,r,x,y,v,urs[cur]);
    }
    else
    {
        if(y<=midy) modify(midx+1,d,l,midy,x,y,v,dls[cur]);
        else modify(midx+1,d,midy+1,r,x,y,v,drs[cur]);
    }
    val[cur]=gcd(gcd(val[uls[cur]],val[urs[cur]]),gcd(val[dls[cur]],val[drs[cur]]));
}
ll query(int U,int D,int L,int R,int u,int d,int l,int r,int cur)
{
    if(U>D||L>R) return 0;
    if(U<=u&&D>=d&&L<=l&&R>=r) return val[cur];
    ll v=0;
    if(U<=midx)
    {
        if(L<=midy) v=gcd(v,query(U,D,L,R,u,midx,l,midy,uls[cur]));
        if(R>midy) v=gcd(v,query(U,D,L,R,u,midx,midy+1,r,urs[cur]));
    }
    if(D>midx)
    {
        if(L<=midy) v=gcd(v,query(U,D,L,R,midx+1,d,l,midy,dls[cur]));
        if(R>midy) v=gcd(v,query(U,D,L,R,midx+1,d,midy+1,r,drs[cur]));
    }
    return v;
}
struct Segment_Tree
{
    ll a[maxn],val[maxn];
    void build(int l,int r,int cur)
    {
        if(l==r)
        {
            val[cur]=a[l];
            return;
        }
        build(l,mid,ls),build(mid+1,r,rs);
        val[cur]=gcd(val[ls],val[rs]);
    }
    void modify(int l,int r,int pos,ll v,int cur)
    {
        if(l==r)
        {
            val[cur]+=v;
            return;
        }
        if(pos<=mid) modify(l,mid,pos,v,ls);
        else modify(mid+1,r,pos,v,rs);
        val[cur]=gcd(val[ls],val[rs]);
    }
    ll query(int L,int R,int l,int r,int cur)
    {
        if(L>R) return 0;
        if(L<=l&&R>=r) return val[cur];
        ll v=0;
        if(L<=mid) v=gcd(v,query(L,R,l,mid,ls));
        if(R>mid) v=gcd(v,query(L,R,mid+1,r,rs));
        return v;
    }
}T1,T2;
int main()
{
    read(n),read(m),read(sx),read(sy),read(q);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            read(a(i,j));
    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j)
            b(i,j)=a(i+1,j+1)-a(i,j+1)-a(i+1,j)+a(i,j);
    for(int i=1;i<n;++i) T1.a[i]=a(i+1,sy)-a(i,sy);
    for(int i=1;i<m;++i) T2.a[i]=a(sx,i+1)-a(sx,i);
    w=a(sx,sy),build(0,n,0,m,root),T1.build(0,n,root),T2.build(0,m,root);
    while(q--)
    {
        int u,d,l,r,opt;
        ll v;
        read(opt),read(u),read(l),read(d),read(r);
        if(!opt)
        {
            u=sx-u,l=sy-l,d=sx+d,r=sy+r;
            v=gcd(w,query(u,d-1,l,r-1,0,n,0,m,root));
            v=gcd(v,gcd(T1.query(u,d-1,0,n,rt),T2.query(l,r-1,0,m,rt)));
            printf("%lld\n",v);
        }
        else
        {
            read(v);
            if(sx>=u&&sx<=d&&sy>=l&&sy<=r) w+=v;
            if(sy>=l&&sy<=r) T1.modify(0,n,u-1,v,rt),T1.modify(0,n,d,-v,rt);
            if(sx>=u&&sx<=d) T2.modify(0,m,l-1,v,rt),T2.modify(0,m,r,-v,rt);
            modify(0,n,0,m,u-1,l-1,v,root),modify(0,n,0,m,d,r,v,root);
            modify(0,n,0,m,u-1,r,-v,root),modify(0,n,0,m,d,l-1,-v,root);
        }
    }
    return 0;
}