BZOJ 2877 膜幻棋盘

发表于 | 更新于

Link

Sengxian大神给出的做法，说实话，确实比Po姐的简洁 虽然Po姐的做法非常直观，但是修改的操作的讨论太繁杂 本来想了一种自己的做法，可以按照Po姐的办法差分而又避免繁杂的讨论，写出来之后怎么也调不对 只好又去研究了一番Sengxian的题解，感觉非常喵

Solution

注意到的主要事实就是gcd(a,b)=gcd(a,b−a)\gcd(a,b)=\gcd(a,b-a)，由此就可以差分来避免区间修改。一维的做法扩展一下，最后就可以推出一个非常优美的二维做法。 Po姐的第二维可变的二维数组写法非常别致啊。。 然后细节比较多，要注意一维和二维线段树查询的边界 改成Sengxian的做法之后，一开始WA了。把二维线段树改成暴力维护矩阵，WA的一样。。 搞了一会儿没办法，把一维线段树也改成暴力了，然后就对了。。 究其原因，是因为一维线段树的边界没有考虑完全，然而一维线段树在二维线段树里是对的，是因为二维线段树的边界判全了。。 这说明，暴露在外直接面向全局的函数一定要判好边界等等特殊情况，被套在里面对了，不代表确实是对的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include "lucida"
using std::max;
using std::min;
const int MAXN=500000+11;
int n,m,X,Y;
int64 gcd(int64 a,int64 b) {
	a=a<0?-a:a;b=b<0?-b:b;
	for(int64 t;b;t=a%b,a=b,b=t);
	return a;
}
struct TwO {
	int step;
	int64 a[MAXN];
	int64 *operator [](int x) {
		return a+(x-1)*step+1;
	}
}imap;
namespace segtree1D {
	const int SIZE=(MAXN<<4)+(MAXN<<3),OPT_COVER=0,OPT_ADD=1;
	struct Node {
		Node *son[2];
		int64 v;
		Node(int64 v):v(v) {
			son[0]=son[1]=0;
		}
		void Up() {
			v=gcd(son[0]->v,son[1]->v);
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
	};
	struct SegTree {
		Node *root;int L,R;
		SegTree(){}
		void Build(Node *&pos,int L,int R,int64 a[]) {
			pos=new Node(a[L]);
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid,a);
				Build(pos->son[1],Mid+1,R,a);
				pos->Up();
			}
		}
		void Edit(Node *pos,int L,int R,int goal,int64 c,int mode) {
			if(L==R) (mode==OPT_COVER)?(pos->v=c):(pos->v+=c);
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Edit(pos->son[0],L,Mid,goal,c,mode);
				else Edit(pos->son[1],Mid+1,R,goal,c,mode);
				pos->Up();
			}
		}
		int64 Access(Node *pos,int L,int R,int l,int r) {
			if(l<=L && R<=r)
				return pos->v;
			else {
				int Mid=(L+R)>>1;
				int64 res=0;
				if(l<=Mid) res=gcd(res,Access(pos->son[0],L,Mid,l,r));
				if(Mid+1<=r) res=gcd(res,Access(pos->son[1],Mid+1,R,l,r));
				return res;
			}
		}

		SegTree(int L,int R,int64 a[]):L(L),R(R) {
			if(L<=R) Build(root,L,R,a);
		}
		SegTree(Node *root,int L,int R):root(root),L(L),R(R) {}
		void Add(int pos,int64 c) {
			if(L<=pos && pos<=R) Edit(root,L,R,pos,c,OPT_ADD);//没判pos.
		}
		void Cover(int pos,int64 c) {
			if(L<=pos && pos<=R) Edit(root,L,R,pos,c,OPT_COVER);
		}
		int64 Qgcd(int l,int r) {
			return L<=R && l<=r?Access(root,L,R,l,r):0;
		}
		int64 Qgcd(int pos) {
			return L<=R?Access(root,L,R,pos,pos):0;
		}
	};
	Node *Merge(Node *p1,Node *p2,int L,int R) {
		Node *pos=new Node(0);
		if(L==R) pos->v=gcd(p1->v,p2->v);
		else {
			int Mid=(L+R)>>1;
			pos->son[0]=Merge(p1->son[0],p2->son[0],L,Mid);
			pos->son[1]=Merge(p1->son[1],p2->son[1],Mid+1,R);
			pos->Up();
		}
		return pos;
	}
}
namespace segtree2D {
	typedef segtree1D::SegTree InnerTree;
	using segtree1D::Merge;
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		InnerTree tr;
		Node() {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
	};
	struct SegTree {
		Node *root;int L,R,IL,IR;
		SegTree(){}
		void Build(Node *&pos,int L,int R,TwO &a) {
			pos=new Node;
			if(L==R) 
				new(&pos->tr) InnerTree(IL,IR,a[L]);
			else {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid,a);
				Build(pos->son[1],Mid+1,R,a);
				new(&pos->tr) InnerTree(Merge(pos->son[0]->tr.root,pos->son[1]->tr.root,IL,IR),IL,IR);
			}
		}
		void Edit(Node *pos,int L,int R,int goal,int ig,int64 c) {
			if(L==R) 
				pos->tr.Add(ig,c);
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Edit(pos->son[0],L,Mid,goal,ig,c);
				else Edit(pos->son[1],Mid+1,R,goal,ig,c);
				pos->tr.Cover(ig,gcd(pos->son[0]->tr.Qgcd(ig),pos->son[1]->tr.Qgcd(ig)));	
			}
		}
		int64 Access(Node *pos,int L,int R,int l,int r,int il,int ir) {
			if(l<=L && R<=r)
				return pos->tr.Qgcd(il,ir);
			else {
				int Mid=(L+R)>>1;int64 res=0;
				if(l<=Mid) res=gcd(res,Access(pos->son[0],L,Mid,l,r,il,ir));
				if(Mid+1<=r) res=gcd(res,Access(pos->son[1],Mid+1,R,l,r,il,ir));
				return res;
			}
		}

		SegTree(int x1,int y1,int x2,int y2,TwO &a):L(x1),R(x2),IL(y1),IR(y2) {
			if(L<=R && IL<=IR) Build(root,L,R,a);
		}
		void Add(int x,int y,int64 c) {
			if(L<=R && IL<=IR && L<=x && x<=R && IL<=y && y<=IR) Edit(root,L,R,x,y,c);
		}
		int64 Qgcd(int x1,int y1,int x2,int y2) {
			return L<=R && IL<=IR && x1<=x2 && y1<=y2?Access(root,L,R,x1,x2,y1,y2):0;
		}
	};
}
typedef segtree1D::SegTree Axis;
typedef segtree2D::SegTree Plane;
Plane pt;Axis xt,yt;int64 origin;
void Build() {
	static TwO pdiff;
	static int64 xdiff[MAXN],ydiff[MAXN];
	pdiff.step=m;
	for(int i=1;i<=n-1;++i)
		for(int j=1;j<=m-1;++j)
			pdiff[i][j]=imap[i+1][j+1]-imap[i+1][j]-imap[i][j+1]+imap[i][j];
	for(int i=1;i<=n-1;++i)
		xdiff[i]=imap[i+1][Y]-imap[i][Y];
	for(int i=1;i<=m;++i)
		ydiff[i]=imap[X][i+1]-imap[X][i];
	origin=imap[X][Y];
	new(&xt) Axis(1,n-1,xdiff);
	new(&yt) Axis(1,m-1,ydiff);
	new(&pt) Plane(1,1,n-1,m-1,pdiff);
}
void Modify(int x1,int y1,int x2,int y2,int64 c) {
	if(x1<=X && X<=x2 && y1<=Y && Y<=y2) 
		origin+=c;
	if(y1<=Y && Y<=y2) {
		xt.Add(x1-1,c);
		xt.Add(x2,-c);
	}
	if(x1<=X && X<=x2) {
		yt.Add(y1-1,c);
		yt.Add(y2,-c);
	}
	pt.Add(x1-1,y1-1,c);
	pt.Add(x1-1,y2,-c);
	pt.Add(x2,y1-1,-c);
	pt.Add(x2,y2,c);
}
int64 Query(int x1,int y1,int x2,int y2) {
	assert(x1<=X && X<=x2 && y1<=Y && Y<=y2);
	int64 res=origin;
	res=gcd(res,xt.Qgcd(x1,x2-1));
	res=gcd(res,yt.Qgcd(y1,y2-1));
	res=gcd(res,pt.Qgcd(x1,y1,x2-1,y2-1));
	return res;
}
int main() {
//	freopen("input","r",stdin);
	is>>n>>m;imap.step=m;
	int Q;is>>X>>Y>>Q;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			is>>imap[i][j];
	Build();
	for(int i=1;i<=Q;++i) {
		int opt,x1,x2,y1,y2;int64 c;
		is>>opt>>x1>>y1>>x2>>y2;
		if(opt==0) 
			os<<Query(X-x1,Y-y1,X+x2,Y+y2)<<'\n';
		else {
			is>>c;
			Modify(x1,y1,x2,y2,c);
		}
	}
	return 0;
}