| 记录编号 |
168852 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOI 2012]魔幻棋盘 |
最终得分 |
100 |
| 用户昵称 |
 ztx |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
4.280 s |
| 提交时间 |
2015-07-06 21:46:35 |
内存使用 |
80.31 MiB |
显示代码纯文本
/****************************************\
* Author : ztx
* Title : [cogs] 965. [NOI2012] 魔幻棋盘
* ALG : 差分+线段树
* CMT :
* Time :
\****************************************/
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
typedef double lf ;
typedef long double llf ;
typedef unsigned uint ;
typedef unsigned long long ull ;
#define StrLen 33554432LL
char Stream[StrLen] , *ptr = Stream ;
#define Getchar() (*ptr++)
//#define Getchar() getchar()
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
ret = NEG = 0 ; while (CH=Getchar() , CH<'!') ;
if (CH == '-') NEG = true , CH = Getchar() ;
while (ret = ret*10+CH-'0' , CH=Getchar() , CH>'!') ;
if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
while (ret=Getchar() , ret<'!') ;
while (CH=Getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
ret[0]=0;while (CH=Getchar() , CH<'!') ;
while (ret[++ret[0]]=CH,CH=Getchar(),CH>'!') ;
ret[ret[0]+1] = 0 ;
}
#define maxn 524288LL
#define maxt 2097152LL
int n , m , ox , oy , qx , qy , qxx , qyy , ql , qr , qd ;
ll data[maxn] = {0} , a[maxn] = {0} , b[2][maxn] = {0} , qw , qa ;
#define data(x,y) data[(x)*m+(y)-m]
#define a(x,y) a[(x)*m+(y)-m]
#define MX ((x1+x2)>>1)
#define MY ((y1+y2)>>1)
#define XL o->c[0],x1,MX,y1,y2,0
#define XR o->c[1],MX+1,x2,y1,y2,0
#define YL o->c[0],x1,x2,y1,MY,1
#define YR o->c[1],x1,x2,MY+1,y2,1
#define l(o) (o<<1)
#define r(o) (o<<1|1)
#define M ((L+R)>>1)
#define left l(o),L,M
#define right r(o),M+1,R
#define SegmentTree_2D root,1,n,1,m
#define SegmentTree_X 1,1,n
#define SegmentTree_Y 1,1,m
ll _gcd_tmp ;
inline ll abss(ll x) { return x<0 ? -x : x ; }
inline ll gcd(ll x,ll y) {
while (y) _gcd_tmp = y , y = x%y , x = _gcd_tmp ;
return abss(x) ;
}
struct KD {
KD *c[2] ; ll sum ;
inline void init() ;
inline void update() ;
} *null = new KD , *root = null ;
inline void KD::init() { sum = 0 , c[0] = c[1] = null ; }
inline void KD::update() { sum = gcd(c[0]->sum,c[1]->sum) ; }
void build(KD*&o,int x1,int x2,int y1,int y2,int d=0) {
if (x1>x2 || y1>y2) return ; o = new KD , o->init() ;
if (x1==x2 && y1==y2) { o->sum = a(x1,y1) ; return ; }
if (d) { build(XL) ; build(XR) ; } else { build(YL) ; build(YR) ; }
o->update() ;
}
void insert(KD*o,int x1,int x2,int y1,int y2,int d=0) {
if (o == null) return ;
if (x1==x2 && y1==y2) { a(qx,qy) += qw , o->sum = a(qx,qy) ; return ; }
if (d) { if (qx <= MX) insert(XL) ; else insert(XR) ; }
else { if (qy <= MY) insert(YL) ; else insert(YR) ; }
o->update() ;
}
inline void Insert(const int&x,const int&y,const ll&w) {
if (x<1 || y<1 || x>=n || y>=m) return ;
qx = x , qy = y , qw = w ;
insert(SegmentTree_2D) ;
}
inline void Query(KD*o,int x1,int x2,int y1,int y2,int d=0) {
if (o==null || !o->sum || x1>qxx || x2<qx || y1>qyy || y2<qy) return ;
if (qx<=x1 && x2<=qxx && qy<=y1 && y2<=qyy) { qa = gcd(qa,o->sum) ; return ; }
if (d) Query(XL) , Query(XR) ; else Query(YL) , Query(YR) ;
}
ll sum[2][maxt] = {0} ;
void build(int o,int L,int R) {
if (L == R) { sum[qd][o] = b[qd][L] ; return ; }
build(left) , build(right) ;
sum[qd][o] = gcd(sum[qd][l(o)],sum[qd][r(o)]) ;
}
void insert(int o,int L,int R) {
if (L == R) { b[qd][L] += qw , sum[qd][o] = b[qd][L] ; return ; }
if (ql<=M) insert(left) ; else insert(right) ;
sum[qd][o] = gcd(sum[qd][l(o)],sum[qd][r(o)]) ;
}
inline void Insert(int x,ll w) {
if (x<1 || (qd && x>=n) || (!qd && x>=m)) return ;
ql = x , qw = w ;
if (qd) insert(SegmentTree_X) ; else insert(SegmentTree_Y) ;
}
inline void Query(int o,int L,int R) {
if (ql<=L && R<=qr) { qa = gcd(qa,sum[qd][o]) ; return ; }
if (ql<=M) Query(left) ; if (qr>M) Query(right) ;
}
int main() {
int T , i , j , cmd , x1 , x2 , y1 , y2 ;
ll w ;
#define READ
#ifdef READ
freopen("chessa.in" ,"r",stdin ) ;
freopen("chessa.out","w",stdout) ;
#endif
fread(Stream,1,StrLen,stdin) ;
null->init() ;
read(n) , read(m) , read(ox) , read(oy) , read(T) ;
Rep (i,1,n) Rep (j,1,m) read(data(i,j)) ;
rep (i,1,n) rep (j,1,m)
a(i,j) = data(i,j)-data(i,j+1)-data(i+1,j)+data(i+1,j+1) ;
rep (i,1,n)
b[1][i] = data(i+1,oy)-data(i,oy) ;
rep (i,1,m)
b[0][i] = data(ox,i+1)-data(ox,i) ;
build(SegmentTree_2D) ;
qd = 1 , build(SegmentTree_X) ;
qd = 0 , build(SegmentTree_Y) ;
while (T --> 0) {
read(cmd) , read(x1) , read(y1) , read(x2) , read(y2) ;
if (cmd) {
read(w) ;
Insert(x1-1,y1-1,w) , Insert(x2,y1-1,-w) , Insert(x1-1,y2,-w) , Insert(x2,y2,w) ;
if (y1<=oy && oy<=y2) qd = 1 , Insert(x1-1,w) , Insert(x2,-w) ;
if (x1<=ox && ox<=x2) qd = 0 , Insert(y1-1,w) , Insert(y2,-w) ;
if (x1<=ox && ox<=x2 && y1<=oy && oy<=y2) data(ox,oy) += w ;
} else {
qx = ox-x1 , qxx = ox+x2-1 , qy = oy-y1 , qyy = oy+y2-1 , qa = 0 ;
if (qx<=qxx && qy<=qyy) Query(SegmentTree_2D) ;
ql = qx , qr = qxx , qd = 1 ;
if (ql <= qr) Query(SegmentTree_X) ;
ql = qy , qr = qyy , qd = 0 ;
if (ql <= qr) Query(SegmentTree_Y) ;
qa = gcd(qa,data(ox,oy)) ;
printf("%lld\n", qa) ;
}
}
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
Getchar() ; Getchar() ;
#endif
return 0 ;
}