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;
}
文章定位：
