题目
题目描述
将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 N行M列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 X 行第 Y列（行与列均从 1 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：
（a）询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。
（b）修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。
游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 19930324 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 100% 的正确率。
为了简化问题，你的程序只需要完成棋盘守护者的 T 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 2^62 - 1 的正整数。
输入输出格式
输入格式：
第一行为两个正整数N,M，表示棋盘的大小。
第二行为两个正整数X,Y，表示棋盘守护者的位置。
第三行仅有一个正整数T，表示棋盘守护者将进行次操作。
接下来N行，每行有M个正整数，用来描述初始时棋盘上每个位置的数。
接下来T行，按操作的时间顺序给出T次操作。每行描述一次操作，以一个数字0或1开头： 若以数字0开头，表示此操作为询问，随后会有四个非负整数x1,y1,x2,y2，表示询问的区域是以棋盘守护者的位置为基础向上扩展x1行，向下扩展y1行，向左扩展x2列，向右扩展y2列得到的矩形区域（详见样例）。 若以数字1开头，表示此操作为修改，随后会有四个正整数x1,y1,x2,y2和一个整数c，表示修改区域的上、下边界分别为第x1,x2行，左、右边界分别为第y1,y2列（详见样例），在此矩形区域内的所有数统一加上c（注意c可能为负数）。
输出格式：
对于每次询问操作，每行输出一个数，表示该区域内所有数的最大公约数。
输入输出样例
输入样例#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 ≤ 100，M ≤ 100，T ≤ 20000。
B 类数据占 40%，满足 N = 1，M ≤ 500000，T ≤ 100000。
C 类数据占 40%，满足 N * M ≤ 500000，T ≤ 100000。
在每类数据中，均有 50% 的数据满足每次修改操作仅含一个格子（即 x1 = x2, y1 = x2）。
输入数据保证满足题目描述中的所有性质。
题解
这题一看就是二维线段树
区间修改简单，但是区间$\gcd$怎么维护是个问题
$\gcd$有一个性质：一堆数的$\gcd$=这堆数差分后的$\gcd$
我们可以通过两个数推广到多个数。设$A=\gcd\times a$
$B=\gcd\times b$
则差分后$B=B-A=b\gcd-a\gcd=(b-a)\gcd$
这两个数的最大公约数还是$\gcd$
然后就可以把这个矩阵差分，然后问题转换为维护一个矩阵里区间$\gcd$+单点修改（差分后修改一个区间变为单点修改）
单点修改需要讨论一堆，这里不再赘述
我写的是四分树难写死了，虽然矩阵查询复杂度是假的效率还不错
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cstdlib>
# define LL long long
# define midl (x1+x2>>1)
# define midr (y1+y2>>1)
# define tll s[k].ll
# define tlr s[k].lr
# define trl s[k].rl
# define trr s[k].rr
# define pu(i,j) (i-1)*m+j
using namespace std;
const int MAX=5e5+1;
struct p{
LL x;
int ll,lr,rl,rr;
}s[MAX<<4];
int n,m,xs,ys,T,tot,rt;
LL a[MAX],b[MAX];
LL Abs(LL x)
{
return x>0?x:-x;
}
LL gcd(LL x,LL y)
{
return y?gcd(y,x%y):Abs(x);
}
LL read()
{
LL x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
void pus(int k)
{
s[k].x=gcd(s[tll].x,gcd(s[tlr].x,gcd(s[trl].x,s[trr].x)));
}
void build(int x1,int y1,int x2,int y2,int &k)
{
if(x1>x2||y1>y2) return;
k=++tot;
if(x1==x2&&y1==y2)
{
s[k].x=a[pu(x1,y1)];
return;
}
build(x1,y1,midl,midr,tll);
build(midl+1,y1,x2,midr,tlr);
build(x1,midr+1,midl,y2,trl);
build(midl+1,midr+1,x2,y2,trr);
pus(k);
}
LL ask(int x1,int y1,int x2,int y2,int k,int X1,int Y1,int X2,int Y2)
{
if(x1>X2||x2<X1||y1>Y2||y2<Y1) return 0;
if(x1>=X1&&x2<=X2&&y1>=Y1&&y2<=Y2) return s[k].x;
return gcd(ask(x1,y1,midl,midr,tll,X1,Y1,X2,Y2),gcd(ask(midl+1,y1,x2,midr,tlr,X1,Y1,X2,Y2),gcd(ask(x1,midr+1,midl,y2,trl,X1,Y1,X2,Y2),ask(midl+1,midr+1,x2,y2,trr,X1,Y1,X2,Y2))));
}
void change(int x1,int y1,int x2,int y2,int k,int X,int Y,LL dis)
{
if(x1==x2&&y1==y2)
{
s[k].x+=dis;
return;
}
if(X<=midl)
if(Y<=midr) change(x1,y1,midl,midr,tll,X,Y,dis);
else change(x1,midr+1,midl,y2,trl,X,Y,dis);
else if(Y<=midr) change(midl+1,y1,x2,midr,tlr,X,Y,dis);
else change(midl+1,midr+1,x2,y2,trr,X,Y,dis);
pus(k);
}
int main()
{
n=read(),m=read(),xs=read(),ys=read(),T=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[pu(i,j)]=read();
for(int i=xs-1;i>=1;--i)
for(int j=1;j<=m;++j)
{
int pos=pu(i,j);
b[pos]=a[pos]-a[pos+m];
}
for(int i=xs+1;i<=n;++i)
for(int j=1;j<=m;++j)
{
int pos=pu(i,j);
b[pos]=a[pos]-a[pos-m];
}
for(int i=1;i<=m;++i)
{
int pos=pu(xs,i);
b[pos]=a[pos];
}
for(int i=1;i<=n;++i)
for(int j=ys-1;j>=1;--j)
{
int pos=pu(i,j);
a[pos]=b[pos]-b[pos+1];
}
for(int i=1;i<=n;++i)
for(int j=ys+1;j<=m;++j)
{
int pos=pu(i,j);
a[pos]=b[pos]-b[pos-1];
}
for(int i=1;i<=n;++i)
{
int pos=pu(i,ys);
a[pos]=b[pos];
}
build(1,1,n,m,rt);
for(int i=1;i<=T;++i)
{
int op=read(),x1=read(),y1=read(),x2=read(),y2=read();
if(!op) printf("%lld\n",ask(1,1,n,m,1,xs-x1,ys-y1,xs+x2,ys+y2));
else if(op==1)
{
LL dis=read();
if(x1<=xs&&y1<=ys&&x2>=xs&&y2>=ys)
{
change(1,1,n,m,1,xs,ys,dis);
if(x1!=1)
{
change(1,1,n,m,1,x1-1,ys,-dis);
if(y1!=1) change(1,1,n,m,1,x1-1,y1-1,dis);
if(y2!=m) change(1,1,n,m,1,x1-1,y2+1,dis);
}
if(x2!=n)
{
change(1,1,n,m,1,x2+1,ys,-dis);
if(y1!=1) change(1,1,n,m,1,x2+1,y1-1,dis);
if(y2!=m) change(1,1,n,m,1,x2+1,y2+1,dis);
}
if(y1!=1) change(1,1,n,m,1,xs,y1-1,-dis);
if(y2!=m) change(1,1,n,m,1,xs,y2+1,-dis);
}
else
{
if(x1<xs&&y1<ys&&x2<xs&&y2<ys)
{
change(1,1,n,m,1,x2,y2,dis);
if(y1!=1&&x1!=1) change(1,1,n,m,1,x1-1,y1-1,dis);
if(y1!=1) change(1,1,n,m,1,x2,y1-1,-dis);
if(x1!=1) change(1,1,n,m,1,x1-1,y2,-dis);
}
else if(x1<xs&&y1>ys&&x2<xs&&y2>ys)
{
change(1,1,n,m,1,x2,y1,dis);
if(y2!=m&&x1!=1) change(1,1,n,m,1,x1-1,y2+1,dis);
if(y2!=m) change(1,1,n,m,1,x2,y2+1,-dis);
if(x1!=1) change(1,1,n,m,1,x1-1,y1,-dis);
}
else if(x1>xs&&y1<ys&&x2>xs&&y2<ys)
{
change(1,1,n,m,1,x1,y2,dis);
if(y1!=1&&x2!=n) change(1,1,n,m,1,x2+1,y1-1,dis);
if(y1!=1) change(1,1,n,m,1,x1,y1-1,-dis);
if(x2!=n) change(1,1,n,m,1,x2+1,y2,-dis);
}
else if(x1>xs&&y1>ys&&x2>xs&&y2>ys)
{
change(1,1,n,m,1,x1,y1,dis);
if(y2!=m&&x2!=n) change(1,1,n,m,1,x2+1,y2+1,dis);
if(y2!=m) change(1,1,n,m,1,x1,y2+1,-dis);
if(x2!=n) change(1,1,n,m,1,x2+1,y1,-dis);
}
else if(x1<=xs&&x2>=xs&&y1<ys&&y2<ys)
{
change(1,1,n,m,1,xs,y2,dis);
if(y1!=1&&x1!=1) change(1,1,n,m,1,x1-1,y1-1,dis);
if(y1!=1&&x2!=n) change(1,1,n,m,1,x2+1,y1-1,dis);
if(y1!=1) change(1,1,n,m,1,xs,y1-1,-dis);
if(x1!=1) change(1,1,n,m,1,x1-1,y2,-dis);
if(x2!=n) change(1,1,n,m,1,x2+1,y2,-dis);
}
else if(x1<=xs&&x2>=xs&&y1>ys&&y2>ys)
{
change(1,1,n,m,1,xs,y1,dis);
if(y2!=m&&x1!=1) change(1,1,n,m,1,x1-1,y2+1,dis);
if(y2!=m&&x2!=n) change(1,1,n,m,1,x2+1,y2+1,dis);
if(y2!=m) change(1,1,n,m,1,xs,y2+1,-dis);
if(x1!=1) change(1,1,n,m,1,x1-1,y1,-dis);
if(x2!=n) change(1,1,n,m,1,x2+1,y1,-dis);
}
else if(x1<xs&&x2<xs&&y1<=ys&&y2>=ys)
{
change(1,1,n,m,1,x2,ys,dis);
if(y1!=1&&x1!=1) change(1,1,n,m,1,x1-1,y1-1,dis);
if(y2!=m&&x1!=1) change(1,1,n,m,1,x1-1,y2+1,dis);
if(y1!=1) change(1,1,n,m,1,x2,y1-1,-dis);
if(x1!=1) change(1,1,n,m,1,x1-1,ys,-dis);
if(y2!=m) change(1,1,n,m,1,x2,y2+1,-dis);
}
else if(x1>xs&&x2>xs&&y1<=ys&&y2>=ys)
{
change(1,1,n,m,1,x1,ys,dis);
if(y1!=1&&x2!=n) change(1,1,n,m,1,x2+1,y1-1,dis);
if(y2!=m&&x2!=n) change(1,1,n,m,1,x2+1,y2+1,dis);
if(y1!=1) change(1,1,n,m,1,x1,y1-1,-dis);
if(x2!=n) change(1,1,n,m,1,x2+1,ys,-dis);
if(y2!=m) change(1,1,n,m,1,x1,y2+1,-dis);
}
}
}
}
return 0;
}
