BZOJ2877 [Noi2012]魔幻棋盘

时间:2023-03-09 15:31:28
BZOJ2877 [Noi2012]魔幻棋盘

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

Description

Input

第一行为两个正整数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可能为负数)。

Output

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

Sample Input

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

Sample Output

6 6

正解:二维线段树+二阶差分

解题报告:

  PoPoQQQ大爷的题解

  这道题非常强啊,细节多的我已经无力吐槽了…

  我写+调花了两个晚上…

  考虑先做一次横向差分,再做一次纵向差分,可以发现差分之后的gcd和原来的gcd相等,但是差分之后我就可以把矩阵修改转换为单点修改了。

  每个矩阵只需修改四个角即可。

  二维线段树维护矩阵gcd。

  注意有不少边界和细节,拍一拍就秒WA,一大堆bug...

  另外,我是靠自己yy的算法写的…

  所以出了一点奇怪的问题,算法被赵爷叉了…不过还是跑过了6个点23333。我开始是特判中心点所在的行、列,单独做,事实上这样是有问题的,只要把四个角落的分别以其中心差分就没有问题了...我调了两个晚上,拍WA了十几次,一次次调...心好累...

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
const int MAXN = 1000011;//数组不要开小了!
int n,m,N,M,X[2],Y[2],cnt,rt,rt2,rt3;
LL lin[MAXN],CC,ans;
struct Array{//不知道每维度大小的情况下的黑科技定义方法 by PoPoQQQ
LL shu[MAXN];
LL* operator [] (int x) { return &shu[(x-1)*m]; }
}ju; struct node{
int ls,rs,l,r,tree;
LL gcd;
}a[MAXN*3]; inline LL gcd(LL x,LL y){ if(y==0) return x; return gcd(y,x%y); } inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline LL getlong(){
LL w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} namespace One_D{
struct node{
int ls,rs,l,r;
LL gcd;
}a[MAXN*3]; inline void build(int &k,int l,int r){
if(!k) k=++cnt; int mid=(l+r)>>1; a[k].l=l; a[k].r=r;
if(l==r) { a[k].gcd=lin[l]; return ; }
build(a[k].ls,l,mid); build(a[k].rs,mid+1,r);
a[k].gcd=gcd(a[a[k].ls].gcd,a[a[k].rs].gcd);
} inline LL query(int k,int l,int r,int ql,int qr){
if(ql>qr) return 0;
if(ql<=l && r<=qr) return a[k].gcd; int mid=(l+r)>>1;
if(ql>mid) return query(a[k].rs,mid+1,r,ql,qr);
else if(qr<=mid) return query(a[k].ls,l,mid,ql,qr);
else return gcd(query(a[k].ls,l,mid,ql,qr),query(a[k].rs,mid+1,r,ql,qr));
} inline void modify(int k,int l,int r,int pos,LL val){
if(l==r) { a[k].gcd+=val; return ; }
int mid=(l+r)>>1;
if(pos<=mid) modify(a[k].ls,l,mid,pos,val); else modify(a[k].rs,mid+1,r,pos,val);
a[k].gcd=gcd(a[a[k].ls].gcd,a[a[k].rs].gcd);
}
} namespace Seg_tree{
inline void build(int &k,int l,int r,int bel){
if(!k) k=++cnt; a[k].l=l; a[k].r=r;
if(l==r) { a[k].gcd=ju[bel][l]; return ; }
int mid=(l+r)>>1; build(a[k].ls,l,mid,bel); build(a[k].rs,mid+1,r,bel);
a[k].gcd=gcd(a[a[k].ls].gcd,a[a[k].rs].gcd);
} inline LL query(int k,int ql,int qr){
if(ql>qr) return 0;
if(ql<=a[k].l && a[k].r<=qr) return a[k].gcd;
int mid=(a[k].l+a[k].r)>>1;
if(ql>mid) return query(a[k].rs,ql,qr);
else if(qr<=mid)/*!!!*/ return query(a[k].ls,ql,qr);
else return gcd(query(a[k].ls,ql,qr),query(a[k].rs,ql,qr));
} inline void modify(int k,int l,int r,int pos,LL val){
if(l==r) { a[k].gcd+=val; return ; } int mid=(l+r)>>1;
if(pos<=mid) modify(a[k].ls,l,mid,pos,val); else modify(a[k].rs,mid+1,r,pos,val);
a[k].gcd=gcd(a[a[k].ls].gcd,a[a[k].rs].gcd);
}
} namespace Two_D{
inline void merge(int &k,int lc,int rc){
if(!k) k=++cnt; a[k].l=a[lc].l; a[k].r=a[lc].r;
if(a[k].l==a[k].r) { a[k].gcd=gcd(a[lc].gcd,a[rc].gcd); return ; }
merge(a[k].ls,a[lc].ls,a[rc].ls);
merge(a[k].rs,a[lc].rs,a[rc].rs);
a[k].gcd=gcd(a[a[k].ls].gcd,a[a[k].rs].gcd);
} inline void build(int &k,int l,int r){
if(!k) k=++cnt; a[k].l=l; a[k].r=r; if(l==r) { Seg_tree::build(a[k].tree,1,m,l); return ; }
int mid=(l+r)>>1; build(a[k].ls,l,mid); build(a[k].rs,mid+1,r);
merge(a[k].tree,a[a[k].ls].tree,a[a[k].rs].tree);
} inline LL query(int k,int l,int r,int zuo,int you,int shang,int xia){
if(zuo>you || shang>xia) return 0;
if(zuo<=l && r<=you) return Seg_tree::query(a[k].tree,shang,xia);
int mid=(l+r)>>1;
if(zuo>mid) return query(a[k].rs,mid+1,r,zuo,you,shang,xia);
else if(you<=mid) return query(a[k].ls,l,mid,zuo,you,shang,xia);
else return gcd(query(a[k].rs,mid+1,r,zuo,you,shang,xia),query(a[k].ls,l,mid,zuo,you,shang,xia));
} inline void modify(int k,int l,int r,int xx,int yy,LL val){
if(l==r) { Seg_tree::modify(a[k].tree,1,m,yy,val); return ; } int mid=(l+r)>>1;
if(xx<=mid) modify(a[k].ls,l,mid,xx,yy,val); else modify(a[k].rs,mid+1,r,xx,yy,val);
LL lg=Seg_tree::query(a[a[k].ls].tree,yy,yy);
LL rg=Seg_tree::query(a[a[k].rs].tree,yy,yy);
LL nowg=Seg_tree::query(a[k].tree,yy,yy);
nowg=gcd(lg,rg)-nowg;
Seg_tree::modify(a[k].tree,1,m,yy,nowg);
}
} using namespace Two_D; inline void work(){
n=getint(); m=getint(); N=getint(); M=getint(); int T=getint();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ju[i][j]=getlong(); for(int i=1;i<=n;i++) {
if(i==N) continue;
for(int j=1;j<M-1;j++) ju[i][j]-=ju[i][j+1];
for(int j=m;j>M+1;j--) ju[i][j]-=ju[i][j-1];
} for(int j=1;j<=m;j++) {
if(j==M) continue;
for(int i=1;i<N-1;i++) ju[i][j]-=ju[i+1][j];
for(int i=n;i>N+1;i--) ju[i][j]-=ju[i-1][j];
} for(int j=1;j<M;j++) ju[N][j]-=ju[N][j+1];
for(int j=m;j>M;j--) ju[N][j]-=ju[N][j-1];
for(int i=1;i<=m;i++) lin[i]=ju[N][i];
One_D::build(rt2,1,m);//build横向的 for(int i=1;i<N;i++) ju[i][M]-=ju[i+1][M];
for(int i=n;i>N;i--) ju[i][M]-=ju[i-1][M];
for(int i=1;i<=n;i++) lin[i]=ju[i][M];
One_D::build(rt3,1,n);//build纵向的 for(int i=1;i<=m;i++) ju[N][i]=0;
for(int i=1;i<=n;i++) ju[i][M]=0; build(rt,1,n);
int ljh;
while(T--) {
ljh=getint(); if(ljh==0) {//query
X[0]=getint(); Y[0]=getint(); X[1]=getint(); Y[1]=getint();
X[0]=N-X[0]; X[1]+=N; Y[0]=M-Y[0]; Y[1]+=M;
ans=query(rt,1,n,X[0],X[1],Y[0],Y[1]);//query 2D if(X[0]<=N && N<=X[1] && Y[0]<=M && Y[1]>=M)//query 横向
ans=gcd(ans,One_D::query(rt2,1,m,Y[0],Y[1]));
if(Y[0]<=M && M<=Y[1] && X[0]<=N && N<=X[1] )//query 纵向
ans=gcd(ans,One_D::query(rt3,1,n,X[0],X[1])); ans=abs(ans);
printf("%lld\n",ans);
}
else{//modify
X[0]=getint(); Y[0]=getint(); X[1]=getint(); Y[1]=getint(); CC=getlong(); //modify 横向
if(X[0]<=N && N<=X[1]) {
if(Y[0]<=M && Y[1]<=M) {
One_D::modify(rt2,1,m,Y[1],CC);
if(Y[0]>1) One_D::modify(rt2,1,m,Y[0]-1,-CC);
if(Y[1]==M && M<m) One_D::modify(rt2,1,m,M+1,-CC);/*!!!*/
}
else if(Y[0]>=M && Y[1]>=M) {
One_D::modify(rt2,1,m,Y[0],CC);
if(Y[1]<m) One_D::modify(rt2,1,m,Y[1]+1,-CC);
if(Y[0]==M && M>1) One_D::modify(rt2,1,m,M-1,-CC);/*!!!*/
}
else {
One_D::modify(rt2,1,m,M,CC);
if(Y[0]>1) One_D::modify(rt2,1,m,Y[0]-1,-CC);
//One_D::modify(rt2,1,m,M+1,CC);//!!!
if(Y[1]<m) One_D::modify(rt2,1,m,Y[1]+1,-CC);
}
} //modify 纵向
if(Y[0]<=M && M<=Y[1]) {
if(X[0]<=N && X[1]<=N) {
One_D::modify(rt3,1,n,X[1],CC);
if(X[0]>1) One_D::modify(rt3,1,n,X[0]-1,-CC);
if(X[1]==N && N<n) One_D::modify(rt3,1,n,N+1,-CC);/*!!!*/
}
else if(X[0]>=N && X[1]>=N) {
One_D::modify(rt3,1,n,X[0],CC);
if(X[1]<n) One_D::modify(rt3,1,n,X[1]+1,-CC);
if(X[0]==N && N>1) One_D::modify(rt3,1,n,N-1,-CC);/*!!!*/
}
else {
One_D::modify(rt3,1,n,N,CC);
if(X[0]>1) One_D::modify(rt3,1,n,X[0]-1,-CC);
//One_D::modify(rt3,1,n,N+1,CC);//!!!
if(X[1]<n) One_D::modify(rt3,1,n,X[1]+1,-CC);
}
} //modify 2D
//大力分类讨论...
if(X[0]<N && Y[0]<M) {//左上
if(X[0]>1 && Y[0]>1) modify(rt,1,n,X[0]-1,Y[0]-1,CC);
if(N>1 && Y[0]>1) modify(rt,1,n,min(X[1],N-1),Y[0]-1,-CC);
if(X[0]>1 && M>1) modify(rt,1,n,X[0]-1,min(Y[1],M-1),-CC);
if(N>1 && M>1) modify(rt,1,n,min(N-1,X[1]),min(M-1,Y[1]),CC);
} if(X[1]>N && Y[0]<M) {//左下
if(N<n && M>1) modify(rt,1,n,max(X[0],N+1),min(Y[1],M-1),CC);/*!!!*/
if(N<n && Y[0]>1) modify(rt,1,n,max(X[0],N+1),Y[0]-1,-CC);
if(X[1]<n && M>1) modify(rt,1,n,X[1]+1,min(Y[1],M-1)/*!!!*/,-CC);
if(X[1]<n && Y[0]>1) modify(rt,1,n,X[1]+1,Y[0]-1,CC);
} if(X[0]<N && Y[1]>M) {//右上
if(N>1 && M<m)/*!!!*/ modify(rt,1,n,min(X[1]/*!!!*/,N-1),max(Y[0],M+1),CC);
if(M<m && X[0]>1) modify(rt,1,n,X[0]-1,max(Y[0]/*!!!*/,M+1),-CC);
if(Y[1]<m && N>1/*!!!*/) modify(rt,1,n,min(X[1],N-1),Y[1]+1,-CC);
if(X[0]>1 && Y[1]<m) modify(rt,1,n,X[0]-1,Y[1]+1,CC);
} if(X[1]>N && Y[1]>M){//右下
if(N<n && M<m) modify(rt,1,n,max(X[0],N+1),max(Y[0],M+1),CC);
if(X[1]<n && M<m/*!!!*/) modify(rt,1,n,X[1]+1,max(Y[0],M+1),-CC);
if(N<n && Y[1]<m) modify(rt,1,n,max(X[0],N+1),Y[1]+1,-CC);
if(X[1]<n && Y[1]<m) modify(rt,1,n,X[1]+1,Y[1]+1,CC);
}
}
}
} int main()
{
work();
return 0;
}