「NOI2012」魔幻棋盘
柒葉灬
2018-12-28 08:36:22
# 一篇题解
-----
看到这题，（这是什么鬼题！！！区间相减？？还要维护$gcd$？？？）就知道我是不可能在考场上写出来的，因为我甚至连最基本的**二维线段树**都不会。
**前置技能**：二维线段树，动态开点线段树
$n=1$的 $ 40 $% 的情况时，给出结论：
$$ gcd(a_1,a_2,a_3,a_4)=gcd(a_1,a_2-a_1,a_3-a_2,a_4-a_3) $$
所以我们只要知道其中的一个$a_1$就行了，因为每次询问一定会有给出的位置$x \ ,\ y$，所以$y$左边的数变为$a_{x}-a_{x+1}$，右边的则是$a_{x}-a_{x-1}$。
这样的好处是什么，这样子修改的时候就可以发现**不是区间修改而是单点修改了**。
--------
转到$100$分的情况，我们可以先横着减一下变成：
$$ \begin{bmatrix} (a_{1,1}-a_{1,2})&(a_{1,2}-a_{1,3})&a_{1,3} \\(a_{2,1}-a_{2,2})&(a_{2,2}-a_{2,3})&a_{2,3}\\(a_{3,1}-a_{3,2})&(a_{3,2}-a_{3,3})&a_{3,3}\end{bmatrix}$$
竖着再减一波：
$$\begin{bmatrix} (a_{1,1}-a_{1,2}-a_{2,1}+a_{2,2} )&(a_{1,2}-a_{1,3}-a_{2,2}+a_{2,3})&(a_{1,3}-a_{2,3})\\(a_{2,1}-a_{2,2}-a_{3,1}+a_{3,2} )&(a_{2,2}-a_{2,3}-a_{3,2}+a_{3,3})&(a_{2,3}-a_{3,3})\\(a_{3,1}-a_{3,2})&(a_{3,2}-a_{3,3})&a_{3,3}\end{bmatrix}$$
得到了式子（只是左上角），发现这样子如果区间修改的话，实际上只是改$4$个地方的值即可，然后按规律找到$8$个不同地区的式子，分类讨论就行了。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
int n,m,x,y,q;
long long gcd(long long a,long long b){
return !b?a:gcd(b,a%b);
}
struct P20{
static const int maxn=105;
long long mp[maxn][maxn];
void solve(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&mp[i][j]);
while(q--){
int opt,x1,y1,x2,y2;
scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
if(opt==0){
x1=max(1,x-x1);
x2=min(n,x+x2);
y1=max(1,y-y1);
y2=min(m,y+y2);
long long ans=mp[x1][y1];
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++){
ans=gcd(ans,mp[i][j]);
}
printf("%lld\n",ans);
}else {
long long c;
scanf("%lld",&c);
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
mp[i][j]+=c;
}
}
}
}p20;
struct P60{
static const int maxn=5e5+5;
long long A[maxn];
struct node{
int l,r;
long long val;
}tree[maxn<<2];
void up(int p){
tree[p].val=gcd(abs(tree[p<<1].val),abs(tree[p<<1|1].val));
}
void build(int l,int r,int p){
tree[p].l=l;
tree[p].r=r;
if(l==r)return (void)(tree[p].val=A[l]);
int mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
up(p);
}
void update(int x,long long pos,int p){
if(tree[p].l==tree[p].r)
return (void)(tree[p].val+=pos);
int mid=tree[p].l+tree[p].r>>1;
if(x<=mid)update(x,pos,p<<1);
else update(x,pos,p<<1|1);
up(p);
}
long long Query(int l,int r,int p){
if(tree[p].l==l&&tree[p].r==r){
return abs(tree[p].val);
}
int mid=tree[p].l+tree[p].r>>1;
if(r<=mid)return Query(l,r,p<<1);
else if(l>mid)return Query(l,r,p<<1|1);
else return gcd(Query(l,mid,p<<1),Query(mid+1,r,p<<1|1));
}
void solve(){
for(int i=1;i<=m;i++)
scanf("%lld",&A[i]);
for(int i=1;i<y;i++)
A[i]-=A[i+1];
for(int i=m;i>y;i--)
A[i]-=A[i-1];
build(1,m,1);
while(q--){
int opt,x1,y1,x2,y2;
scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
if(opt==0){
y1=max(1,y-y1);
y2=min(m,y+y2);
long long ans=Query(y1,y2,1);
printf("%lld\n",ans);
}else {
long long c;
scanf("%lld",&c);
if(y1<=y&&y<=y2)update(y,c,1);
if(y1<=y&&y1>1)update(y1-1,-c,1);
else if(y1>y)update(y1,c,1);
if(y2>=y&&y2<m)update(y2+1,-c,1);
else if(y2<y)update(y2,c,1);
}
}
}
}p60;
struct P100{
static const int maxn=5e5+5;
#define A(i,j) mp[(i-1)*m+j]
struct SegTree{
long long mp[maxn];
int Rt,tot,son[maxn<<4][4];
struct node{
int x1,y1,x2,y2;
long long val;
}tree[maxn<<4];
void up(int rt){
tree[rt].val=gcd(gcd(abs(tree[son[rt][0]].val),abs(tree[son[rt][1]].val)),gcd(abs(tree[son[rt][2]].val),abs(tree[son[rt][3]].val)));
}
void build(int &rt,int x1,int y1,int x2,int y2){
if(x1>x2||y1>y2)return;
rt=++tot;
tree[rt]=(node){x1,y1,x2,y2,0};
if(x1==x2&&y1==y2){
long long pos;
int X=x1,Y=y1;
if(X<x){
if(Y<y)pos=A(X,Y)-A(X+1,Y)-A(X,Y+1)+A(X+1,Y+1);
else if(Y>y)pos=A(X,Y)-A(X+1,Y)-A(X,Y-1)+A(X+1,Y-1);
else pos=A(X,Y)-A(X+1,Y);
}else if(X>x){
if(Y<y)pos=A(X,Y)-A(X-1,Y)-A(X,Y+1)+A(X-1,Y+1);
else if(Y>y)pos=A(X,Y)-A(X-1,Y)-A(X,Y-1)+A(X-1,Y-1);
else pos=A(X,Y)-A(X-1,Y);
}else {
if(Y<y)pos=A(X,Y)-A(X,Y+1);
else if(Y>y)pos=A(X,Y)-A(X,Y-1);
else pos=A(X,Y);
}
return (void)(tree[rt].val=pos);
}
int mx=x1+x2>>1,my=y1+y2>>1;
build(son[rt][0],x1,y1,mx,my);
build(son[rt][1],x1,my+1,mx,y2);
build(son[rt][2],mx+1,y1,x2,my);
build(son[rt][3],mx+1,my+1,x2,y2);
up(rt);
}
void update(int x,int y,long long pos,int rt){
if(tree[rt].x1==tree[rt].x2&&tree[rt].y1==tree[rt].y2)
return (void)(tree[rt].val+=pos);
int mx=tree[rt].x1+tree[rt].x2>>1;
int my=tree[rt].y1+tree[rt].y2>>1;
if(x<=mx){
if(y<=my)update(x,y,pos,son[rt][0]);
else update(x,y,pos,son[rt][1]);
}else {
if(y<=my)update(x,y,pos,son[rt][2]);
else update(x,y,pos,son[rt][3]);
}
up(rt);
}
long long Query(int x1,int y1,int x2,int y2,int rt){
if(tree[rt].x1==0)return 0;
if(tree[rt].x1>=x1&&tree[rt].x2<=x2&&tree[rt].y1>=y1&&tree[rt].y2<=y2){
return abs(tree[rt].val);
}
int mx=tree[rt].x1+tree[rt].x2>>1;
int my=tree[rt].y1+tree[rt].y2>>1;
long long ans=0;
if(x1<=mx&&y1<=my)ans=gcd(Query(x1,y1,x2,y2,son[rt][0]),ans);
if(x1<=mx&&y2>my)ans=gcd(Query(x1,y1,x2,y2,son[rt][1]),ans);
if(x2>mx&&y1<=my)ans=gcd(Query(x1,y1,x2,y2,son[rt][2]),ans);
if(x2>mx&&y2>my)ans=gcd(Query(x1,y1,x2,y2,son[rt][3]),ans);
return ans;
}
void upd(int x,int y,long long pos){
if(x<1||y<1||x>n||y>m)return;
update(x,y,pos,1);
}
}S;
void update(int x1,int y1,int x2,int y2,long long c){
if(x2<x){
if(y2<y){
S.upd(x1-1,y1-1,c);
S.upd(x2,y1-1,-c);
S.upd(x1-1,y2,-c);
S.upd(x2,y2,c);
}else if(y1>y){
S.upd(x1-1,y2+1,c);
S.upd(x1-1,y1,-c);
S.upd(x2,y2+1,-c);
S.upd(x2,y1,c);
}else {
S.upd(x1-1,y1-1,c);
S.upd(x2,y1-1,-c);
S.upd(x1-1,y2+1,c);
S.upd(x2,y2+1,-c);
S.upd(x1-1,y,-c);
S.upd(x2,y,c);
}
}else if(x1>x){
if(y2<y){
S.upd(x2+1,y1-1,c);
S.upd(x1,y1-1,-c);
S.upd(x2+1,y2,-c);
S.upd(x1,y2,c);
}else if(y1>y){
S.upd(x2+1,y2+1,c);
S.upd(x2+1,y1,-c);
S.upd(x1,y2+1,-c);
S.upd(x1,y1,c);
}else {
S.upd(x2+1,y1-1,c);
S.upd(x1,y1-1,-c);
S.upd(x2+1,y2+1,c);
S.upd(x1,y2+1,-c);
S.upd(x1,y,c);
S.upd(x2+1,y,-c);
}
}else {
if(y2<y){
S.upd(x1-1,y1-1,c);
S.upd(x1-1,y2,-c);
S.upd(x2+1,y1-1,c);
S.upd(x2+1,y2,-c);
S.upd(x,y1-1,-c);
S.upd(x,y2,c);
}else if(y1>y){
S.upd(x1-1,y2+1,c);
S.upd(x1-1,y1,-c);
S.upd(x2+1,y2+1,c);
S.upd(x2+1,y1,-c);
S.upd(x,y1,c);
S.upd(x,y2+1,-c);
}else {
S.upd(x1-1,y1-1,c);
S.upd(x1-1,y2+1,c);
S.upd(x2+1,y1-1,c);
S.upd(x2+1,y2+1,c);
S.upd(x,y,c);
S.upd(x,y1-1,-c);
S.upd(x,y2+1,-c);
S.upd(x1-1,y,-c);
S.upd(x2+1,y,-c);
}
}
}
void solve(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&S.A(i,j));
S.build(S.Rt,1,1,n,m);
int opt,x1,y1,x2,y2;
while(q--){
scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
if(opt==1){
long long c;
scanf("%lld",&c);
update(x1,y1,x2,y2,c);
}else {
x1=x-x1;y1=y-y1;
x2=x+x2;y2=y+y2;
printf("%lld\n",S.Query(x1,y1,x2,y2,1));
}
}
}
}p100;
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
cin>>n>>m>>x>>y>>q;
if(n<=100&&m<=100)p20.solve();
else if(n==1)p60.solve();
else p100.solve();
return 0;
}
```
------
>题外话，注意是动态开点，如果是四叉树则会开成$max(n,m) * max(n,m)$矩阵的线段树了。