UVA 11992 - Fast Matrix Operations
给定一个r*c(r<=20,r*c<=1e6)的矩阵，其元素都是0，现在对其子矩阵进行操作。
1 x1 y1 x2 y2 val 表示将(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素add上val；
2 x1 y1 x2 y2 val 表示将(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素set为val；
3 x1 y1 x2 y2 val 表示输出(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素的sum，最大最小值max,min;
思路：线段树区间更新+lazy
每行维护一个线段树，然后，线段树维护四个值，max，min,sum，set，add。如果当前set，add都有值，那么先操作set再add,复杂度(n*log(n));
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<queue>
6 #include<stack>
7 #include<math.h>
8 using namespace std;
9 typedef long long LL;
10 typedef struct node
11 {
12 int addv;
13 int setv;
14 int maxx;
15 int minn;
16 int sum;
17 int l;
18 int r;
19 node()
20 {
21 addv = 0;
22 setv = 0;
23 maxx = 0;
24 sum = 0;
25 }
26 } tr;
27 tr tree[30][100005*8];
28 tr flag[100005*8];
29 void build(int l,int r,int k);
30 void update(int k,int id);
31 void add(int l,int r,int k,int nn,int mm,int id,int a);
32 void sett(int l,int r,int k,int nn,int mm,int id,int a);
33 int asksum(int l,int r,int k,int nn,int mm,int id);
34 int askminn(int l,int r,int k,int nn,int mm,int id);
35 int askmaxx(int l,int r,int k,int nn,int mm,int id);
36 int main(void)
37 {
38 int n,m,q;
39 while(scanf("%d %d %d",&n,&m,&q)!=EOF)
40 { memset(tree,0,sizeof(tree));
41 memset(flag,0,sizeof(flag));build(1,m,0);
42 while(q--)
43 {
44 int val ;
45 scanf("%d",&val);
46 if(val == 1)
47 {
48 int x1,y1,x2,y2,v;
49 scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&v);
50 int i,j;
51 for(i = x1;i <= x2;i++)
52 {
53 add(y1,y2,0,1,m,i,v);
54 }
55 }
56 else if(val == 2)
57 {
58 int x1,y1,x2,y2,v;int i,j;
59 scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&v);
60 for(i = x1;i <= x2;i++)
61 {
62 sett(y1,y2,0,1,m,i,v);
63 }
64 }
65 else
66 {
67 int x1,y1,x2,y2;int i,j;
68 scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
69 int su = 0;int ma = 0;int mi = 1e9;
70 for(i = x1;i <= x2;i++)
71 {
72 su += asksum(y1,y2,0,1,m,i);
73 ma = max(askmaxx(y1,y2,0,1,m,i),ma);
74 mi = min(mi,askminn(y1,y2,0,1,m,i));
75 }
76 printf("%d %d %d\n",su,mi,ma);
77 }
78 }
79 }
80 return 0;
81 }
82 void build(int l,int r,int k)
83 {
84 if(l == r)
85 {
86 flag[k].l = l;
87 flag[k].r = r;
88 return ;
89 }
90 else
91 {
92 flag[k].l = l;
93 flag[k].r = r;
94 build(l,(l+r)/2,2*k+1);
95 build((l+r)/2+1,r,2*k+2);
96 }
97 }
98 void update(int k,int id)
99 {
100 while(k>0)
101 {
102 k = (k-1)/2;
103 int x1 = 2*k+1;
104 int x2 = 2*k+2;
105 if(tree[id][x1].setv)
106 { //printf("1\n");
107 int xx1 = x1;
108 tree[id][2*xx1+1].setv = tree[id][x1].setv;
109 tree[id][2*xx1+2].setv = tree[id][x1].setv;
110 tree[id][2*xx1+1].addv = tree[id][x1].addv;
111 tree[id][2*xx1+2].addv = tree[id][x1].addv;
112 tree[id][x1].maxx = tree[id][x1].setv + tree[id][x1].addv;
113 tree[id][x1].minn = tree[id][x1].setv + tree[id][x1].addv;
114 tree[id][x1].sum = tree[id][x1].maxx*(flag[x1].r-flag[x1].l+1);
115 tree[id][x1].setv = 0;
116 tree[id][x1].addv = 0;
117 }
118 else if(tree[id][x1].addv)
119 {
120 int xx1 = x1;
121 tree[id][2*xx1+1].addv += tree[id][x1].addv;
122 tree[id][2*xx1+2].addv += tree[id][x1].addv;
123 tree[id][x1].maxx = tree[id][x1].maxx + tree[id][x1].addv;
124 tree[id][x1].minn = tree[id][x1].minn + tree[id][x1].addv;
125 tree[id][x1].sum += (flag[x1].r-flag[x1].l+1)*(tree[id][x1].addv);
126 tree[id][x1].setv = 0;
127 tree[id][x1].addv = 0;
128 }
129 if(tree[id][x2].setv)
130 {
131 int xx1 = x2;
132 tree[id][2*xx1+1].setv = tree[id][x2].setv;
133 tree[id][2*xx1+2].setv = tree[id][x2].setv;
134 tree[id][2*xx1+1].addv = tree[id][x2].addv;
135 tree[id][2*xx1+2].addv = tree[id][x2].addv;
136 tree[id][x2].maxx = tree[id][x2].setv + tree[id][x2].addv;
137 tree[id][x2].minn = tree[id][x2].setv + tree[id][x2].addv;
138 tree[id][x2].sum = tree[id][x2].maxx*(flag[x2].r-flag[x2].l+1);
139 tree[id][x2].setv = 0;
140 tree[id][x2].addv = 0;
141 }
142 else if(tree[id][x2].addv)
143 { //printf("%d\n",1);
144 int xx1 = x2;
145 tree[id][2*xx1+1].addv += tree[id][x2].addv;
146 tree[id][2*xx1+2].addv += tree[id][x2].addv;
147 tree[id][x2].maxx = tree[id][x2].maxx + tree[id][x2].addv;
148 tree[id][x2].minn = tree[id][x2].minn + tree[id][x2].addv;
149 tree[id][x2].sum += (flag[x2].r-flag[x2].l+1)*(tree[id][x2].addv);
150 tree[id][x2].setv = 0;
151 tree[id][x2].addv = 0;
152 }
153 tree[id][k].maxx = max(tree[id][x1].maxx,tree[id][x2].maxx);
154 tree[id][k].minn = min(tree[id][x1].minn,tree[id][x2].minn);
155 tree[id][k].sum = tree[id][x1].sum+tree[id][x2].sum;
156 }
157 }
158 void add(int l,int r,int k,int nn,int mm,int id,int a)
159 {
160 if(l > mm||r < nn)
161 return ;
162 else if(l <= nn&&r >= mm)
163 {
164 tree[id][k].addv += a;
165 if(tree[id][k].setv )
166 {
167 tree[id][2*k+1].setv = tree[id][k].setv;
168 tree[id][2*k+2].setv = tree[id][k].setv;
169 tree[id][2*k+1].addv = tree[id][k].addv;
170 tree[id][2*k+2].addv = tree[id][k].addv;
171 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);
172 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;
173 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;
174 tree[id][k].setv = 0;
175 tree[id][k].addv = 0;
176 // update(k,id);
177 }
178 else
179 {
180 tree[id][2*k+1].addv += tree[id][k].addv;
181 tree[id][2*k+2].addv += tree[id][k].addv;
182 //printf("%d\n",tree[id][2*k+1].addv);
183 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;
184 tree[id][k].maxx += tree[id][k].addv;
185 tree[id][k].minn += tree[id][k].addv;
186 tree[id][k].addv = 0;
187 //printf("%d\n",tree[id][k].sum);
188 }
189 update(k,id);
190 }
191 else
192 {
193 if(tree[id][k].setv)
194 {
195 tree[id][2*k+1].setv = tree[id][k].setv;
196 tree[id][2*k+2].setv = tree[id][k].setv;
197 tree[id][2*k+1].addv = tree[id][k].addv;
198 tree[id][2*k+2].addv = tree[id][k].addv;
199 tree[id][k].setv = 0;
200 tree[id][k].addv = 0;
201 }
202 else if(tree[id][k].addv)
203 {
204 tree[id][2*k+1].addv += tree[id][k].addv ;
205 tree[id][2*k+2].addv += tree[id][k].addv;
206 tree[id][k].addv = 0;
207 }
208 add(l,r,2*k+1,nn,(nn+mm)/2,id,a);
209 add(l,r,2*k+2,(nn+mm)/2+1,mm,id,a);
210 }
211 }
212 void sett(int l,int r,int k,int nn,int mm,int id,int a)
213 {
214 if(l > mm||r < nn)
215 return ;
216 else if(l <= nn&&r >= mm)
217 {
218 tree[id][k].setv = a;
219 if(tree[id][k].setv != 0)
220 {
221 tree[id][k].addv = 0;
222 tree[id][2*k+1].setv = tree[id][k].setv;
223 tree[id][2*k+2].setv = tree[id][k].setv;
224 tree[id][2*k+1].addv = tree[id][k].addv;
225 tree[id][2*k+2].addv = tree[id][k].addv;
226 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);
227 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;
228 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;
229 tree[id][k].setv = 0;
230 tree[id][k].addv = 0;
231 }
232 update(k,id);
233 }
234 else
235 {
236 if(tree[id][k].setv)
237 {
238 tree[id][2*k+1].setv = tree[id][k].setv;
239 tree[id][2*k+2].setv = tree[id][k].setv;
240 tree[id][2*k+1].addv = tree[id][k].addv;
241 tree[id][2*k+2].addv = tree[id][k].addv;
242 tree[id][k].setv = 0;
243 tree[id][k].addv = 0;
244 }
245 else if(tree[id][k].addv)
246 {
247 tree[id][2*k+1].addv += tree[id][k].addv ;
248 tree[id][2*k+2].addv += tree[id][k].addv;
249 tree[id][k].addv = 0;
250 }
251 sett(l,r,2*k+1,nn,(nn+mm)/2,id,a);
252 sett(l,r,2*k+2,(nn+mm)/2+1,mm,id,a);
253 }
254 }
255 int asksum(int l,int r,int k,int nn,int mm,int id)
256 {
257 if(l>mm||r<nn)
258 return 0;
259 else if(l <= nn&&r>=mm)
260 { //printf("%d %d\n",id,k);
261 if(tree[id][k].setv )
262 {
263 tree[id][2*k+1].setv = tree[id][k].setv;
264 tree[id][2*k+2].setv = tree[id][k].setv;
265 tree[id][2*k+1].addv = tree[id][k].addv;
266 tree[id][2*k+2].addv = tree[id][k].addv;
267 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);
268 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;
269 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;
270 tree[id][k].setv = 0;
271 tree[id][k].addv = 0; update(k,id);
272 }
273 else if(tree[id][k].addv)
274 {
275 tree[id][2*k+1].addv += tree[id][k].addv;
276 tree[id][2*k+2].addv += tree[id][k].addv;
277 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;
278 tree[id][k].maxx += tree[id][k].addv;
279 tree[id][k].minn += tree[id][k].addv;
280 tree[id][k].addv = 0; update(k,id);
281 }
282 return tree[id][k].sum;
283 }
284 else
285 {
286 if(tree[id][k].setv)
287 {
288 tree[id][2*k+1].setv = tree[id][k].setv;
289 tree[id][2*k+2].setv = tree[id][k].setv;
290 tree[id][2*k+1].addv = tree[id][k].addv;
291 tree[id][2*k+2].addv = tree[id][k].addv;
292 tree[id][k].setv = 0;
293 tree[id][k].addv = 0;
294 }
295 else if(tree[id][k].addv)
296 {
297 tree[id][2*k+1].addv += tree[id][k].addv ;
298 tree[id][2*k+2].addv += tree[id][k].addv;
299 tree[id][k].addv = 0;
300 }
301 int nx = asksum(l,r,2*k+1,nn,(nn+mm)/2,id);
302 int ny = asksum(l,r,2*k+2,(nn+mm)/2+1,mm,id);
303 return nx+ny;
304 }
305
306 }
307 int askminn(int l,int r,int k,int nn,int mm,int id)
308 {
309 if(l>mm||r<nn)
310 return 1e9;
311 else if(l <= nn&&r>=mm)
312 {
313 if(tree[id][k].setv != 0)
314 {
315 tree[id][2*k+1].setv = tree[id][k].setv;
316 tree[id][2*k+2].setv = tree[id][k].setv;
317 tree[id][2*k+1].addv = tree[id][k].addv;
318 tree[id][2*k+2].addv = tree[id][k].addv;
319 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);
320 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;
321 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;
322 tree[id][k].setv = 0;
323 tree[id][k].addv = 0; update(k,id);
324 }
325 else if(tree[id][k].addv)
326 {
327 tree[id][2*k+1].addv += tree[id][k].addv;
328 tree[id][2*k+2].addv += tree[id][k].addv;
329 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;
330 tree[id][k].maxx += tree[id][k].addv;
331 tree[id][k].minn += tree[id][k].addv;
332 tree[id][k].addv = 0; update(k,id);
333 }
334 // update(k,id);
335 return tree[id][k].minn;
336 }
337 else
338 {
339 if(tree[id][k].setv)
340 {
341 tree[id][2*k+1].setv = tree[id][k].setv;
342 tree[id][2*k+2].setv = tree[id][k].setv;
343 tree[id][2*k+1].addv = tree[id][k].addv;
344 tree[id][2*k+2].addv = tree[id][k].addv;
345 tree[id][k].setv = 0;
346 tree[id][k].addv = 0;
347 }
348 else if(tree[id][k].addv)
349 {
350 tree[id][2*k+1].addv += tree[id][k].addv ;
351 tree[id][2*k+2].addv += tree[id][k].addv;
352 tree[id][k].addv = 0;
353 }
354 int nx = askminn(l,r,2*k+1,nn,(nn+mm)/2,id);
355 int ny = askminn(l,r,2*k+2,(nn+mm)/2+1,mm,id);
356 return min(nx,ny);
357 }
358 }
359 int askmaxx(int l,int r,int k,int nn,int mm,int id)
360 {
361 if(l>mm||r<nn)
362 return 0;
363 else if(l <= nn&&r>=mm)
364 {
365 if(tree[id][k].setv != 0)
366 {
367 tree[id][2*k+1].setv = tree[id][k].setv;
368 tree[id][2*k+2].setv = tree[id][k].setv;
369 tree[id][2*k+1].addv = tree[id][k].addv;
370 tree[id][2*k+2].addv = tree[id][k].addv;
371 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);
372 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;
373 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;
374 tree[id][k].setv = 0;
375 tree[id][k].addv = 0; update(k,id);
376 }
377 else if(tree[id][k].addv)
378 {
379 tree[id][2*k+1].addv += tree[id][k].addv;
380 tree[id][2*k+2].addv += tree[id][k].addv;
381 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;
382 tree[id][k].maxx += tree[id][k].addv;
383 tree[id][k].minn += tree[id][k].addv;
384 tree[id][k].addv = 0; update(k,id);
385 }
386 //update(k,id);
387 return tree[id][k].maxx;
388 }
389 else
390 {
391 if(tree[id][k].setv)
392 {
393 tree[id][2*k+1].setv = tree[id][k].setv;
394 tree[id][2*k+2].setv = tree[id][k].setv;
395 tree[id][2*k+1].addv = tree[id][k].addv;
396 tree[id][2*k+2].addv = tree[id][k].addv;
397 tree[id][k].setv = 0;
398 tree[id][k].addv = 0;
399 }
400 else if(tree[id][k].addv)
401 {
402 tree[id][2*k+1].addv += tree[id][k].addv ;
403 tree[id][2*k+2].addv += tree[id][k].addv;
404 tree[id][k].addv = 0;
405 }
406 int nx = askmaxx(l,r,2*k+1,nn,(nn+mm)/2,id);
407 int ny = askmaxx(l,r,2*k+2,(nn+mm)/2+1,mm,id);
408 return max(nx,ny);
409 }
410 }