Problem F
Fast Matrix Operations
There is a matrix containing at most 106 elements divided
into r rows and c columns. Each element has a location (x,y) where
1<=x<=r,1<=y<=c. Initially, all the elements are zero. You
need to handle four kinds of operations:
1 x1 y1 x2 y2 v
Increment each element (x,y) in submatrix (x1,y1,x2,y2) by v (v>0)
2 x1 y1 x2 y2 v
Set each element (x,y) in submatrix (x1,y1,x2,y2) to v
3 x1 y1 x2 y2
Output the summation, min value and max value of submatrix (x1,y1,x2,y2)
In the above descriptions, submatrix (x1,y1,x2,y2) means all the
elements (x,y) satisfying x1<=x<=x2 and y1<=x<=y2. It is
guaranteed that 1<=x1<=x2<=r, 1<=y1<=y2<=c. After any
operation, the sum of all the elements in the matrix does not exceed 109.
Input
There are several test cases. The first line of each case contains
three positive integers r, c, m, where m (1<=m<=20,000) is the
number of operations. Each of the next m lines contains a query. There
will be at most twenty rows in the matrix. The input is terminated by
end-of-file (EOF). The size of input file does not exceed 500KB.
Output
For each type-3 query, print the summation, min and max.
Sample Input
4 4 8
1 1 2 4 4 5
3 2 1 4 4
1 1 1 3 4 2
3 1 2 4 4
3 1 1 3 4
2 2 1 4 4 2
3 1 2 4 4
1 1 1 4 3 3
Output for the Sample Input
45 0 5
78 5 7
69 2 7
39 2 7
Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua University
Special Thanks: Yeji Shen, Dun Liang
Note: Please make sure to test your program with the gift I/O files before submitting!
終於用 四分樹v2 敲掉 11992 - Fast Matrix Operations，
那個常數卡得緊，差點就 TLE 了。
如果使用四分樹去解，這個不固定的長寬二維空間，
小心編號的設定，資料結構教一維空間的父節點 k, 2k, 2k+1
或許自然而然地會使用在二維空間 k, 4k-2, 4k-1, 4k, 4k+1
我愚蠢地落入了退化一維空間的形態，此時會浪費非常多空間，
而導致記憶體過大，因而最後得到 Runtime error。
#include <stdio.h>
#include <algorithm>
using namespace std;
#define INF 0x7fffffff
#define MaxN 1000005
struct Node {
int mxv, mnv, sum;
int add, set;
int son[4];
};
Node tree[MaxN<<2];
int NSize;
void build(int k, int lx, int rx, int ly, int ry) {
tree[k].mxv = tree[k].mnv = tree[k].sum = 0;
tree[k].add = tree[k].set = 0;
tree[k].son[0] = tree[k].son[1] =
tree[k].son[2] = tree[k].son[3] = 0; // NULL ptr
if(lx == rx && ly == ry)
return;
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
if(lx <= mx) {
if(ly <= my) {
tree[k].son[0] = ++NSize;
build(NSize, lx, mx, ly, my);
}
if(ry > my) {
tree[k].son[1] = ++NSize;
build(NSize, lx, mx, my+1, ry);
}
}
if(rx > mx) {
if(ly <= my) {
tree[k].son[2] = ++NSize;
build(NSize, mx+1, rx, ly, my);
}
if(ry > my) {
tree[k].son[3] = ++NSize;
build(NSize, mx+1, rx, my+1, ry);
}
}
}
#define downop1(k, v) {tree[k].add = 0; tree[k].set = tree[k].mxv = tree[k].mnv = v;}
#define downop2(k, v) {tree[k].add += v, tree[k].mxv += v, tree[k].mnv += v;}
void pushDown(int k, int lx, int rx, int ly, int ry) {
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
if(tree[k].set) {
if(tree[k].son[0]) {
tree[tree[k].son[0]].sum = (mx-lx+1)*(my-ly+1)*tree[k].set;
downop1(tree[k].son[0], tree[k].set);
}
if(tree[k].son[1]) {
tree[tree[k].son[1]].sum = (mx-lx+1)*(ry-my)*tree[k].set;
downop1(tree[k].son[1], tree[k].set);
}
if(tree[k].son[2]) {
tree[tree[k].son[2]].sum = (rx-mx)*(my-ly+1)*tree[k].set;
downop1(tree[k].son[2], tree[k].set);
}
if(tree[k].son[3]) {
tree[tree[k].son[3]].sum = (rx-mx)*(ry-my)*tree[k].set;
downop1(tree[k].son[3], tree[k].set);
}
tree[k].set = 0;
}
if(tree[k].add) {
if(tree[k].son[0]) {
tree[tree[k].son[0]].sum += (mx-lx+1)*(my-ly+1)*tree[k].add;
downop2(tree[k].son[0], tree[k].add);
}
if(tree[k].son[1]) {
tree[tree[k].son[1]].sum += (mx-lx+1)*(ry-my)*tree[k].add;
downop2(tree[k].son[1], tree[k].add);
}
if(tree[k].son[2]) {
tree[tree[k].son[2]].sum += (rx-mx)*(my-ly+1)*tree[k].add;
downop2(tree[k].son[2], tree[k].add);
}
if(tree[k].son[3]) {
tree[tree[k].son[3]].sum += (rx-mx)*(ry-my)*tree[k].add;
downop2(tree[k].son[3], tree[k].add);
}
tree[k].add = 0;
}
}
void pushUp(int k) {
tree[k].mxv = 0;
tree[k].mnv = INF;
tree[k].sum = 0;
if(tree[k].son[0]) {
tree[k].sum += tree[tree[k].son[0]].sum;
tree[k].mxv = max(tree[k].mxv, tree[tree[k].son[0]].mxv);
tree[k].mnv = min(tree[k].mnv, tree[tree[k].son[0]].mnv);
}
if(tree[k].son[1]) {
tree[k].sum += tree[tree[k].son[1]].sum;
tree[k].mxv = max(tree[k].mxv, tree[tree[k].son[1]].mxv);
tree[k].mnv = min(tree[k].mnv, tree[tree[k].son[1]].mnv);
}
if(tree[k].son[2]) {
tree[k].sum += tree[tree[k].son[2]].sum;
tree[k].mxv = max(tree[k].mxv, tree[tree[k].son[2]].mxv);
tree[k].mnv = min(tree[k].mnv, tree[tree[k].son[2]].mnv);
}
if(tree[k].son[3]) {
tree[k].sum += tree[tree[k].son[3]].sum;
tree[k].mxv = max(tree[k].mxv, tree[tree[k].son[3]].mxv);
tree[k].mnv = min(tree[k].mnv, tree[tree[k].son[3]].mnv);
}
}
int op_v, op_argv;
int SUM, MXV, MNV;
void modify(int k, int lx, int rx, int ly, int ry, int a, int b, int c, int d) {
if(a <= lx && rx <= b && c <= ly && ry <= d) {
if(op_v == 0) {
SUM += tree[k].sum;
MXV = max(MXV, tree[k].mxv);
MNV = min(MNV, tree[k].mnv);
} else if(op_v == 1) {
tree[k].add += op_argv;
tree[k].mxv += op_argv;
tree[k].mnv += op_argv;
tree[k].sum += op_argv*(rx-lx+1)*(ry-ly+1);
} else if(op_v == 2) {
tree[k].add = 0;
tree[k].set = tree[k].mxv = tree[k].mnv = op_argv;
tree[k].sum = op_argv*(rx-lx+1)*(ry-ly+1);
}
return;
}
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
pushDown(k, lx, rx, ly, ry);
if(a <= mx) {
if(c <= my) {
if(tree[k].son[0]) {
modify(tree[k].son[0], lx, mx, ly, my, a, b, c, d);
}
}
if(d > my) {
if(tree[k].son[1]) {
modify(tree[k].son[1], lx, mx, my+1, ry, a, b, c, d);
}
}
}
if(b > mx) {
if(c <= my) {
if(tree[k].son[2]) {
modify(tree[k].son[2], mx+1, rx, ly, my, a, b, c, d);
}
}
if(d > my) {
if(tree[k].son[3]) {
modify(tree[k].son[3], mx+1, rx, my+1, ry, a, b, c, d);
}
}
}
if(op_v)
pushUp(k);
}
int main() {
int r, c, q;
int lx, ly, rx, ry;
while(scanf("%d %d %d", &r, &c, &q) == 3) {
NSize = 1;
build(1, 1, r, 1, c);
while(q--) {
scanf("%d %d %d %d %d", &op_v, &lx, &ly, &rx, &ry);
if(op_v == 1)
scanf("%d", &op_argv);
else if(op_v == 2)
scanf("%d", &op_argv);
else
op_v = 0, SUM = 0, MXV = 0, MNV = INF;
modify(1, 1, r, 1, c, lx, rx, ly, ry);
if(op_v == 0)
printf("%d %d %d\n", SUM, MNV, MXV);
}
}
return 0;
}
文章定位：
