UVA - 11992（线段树~~顺便吐槽为何我最近总遇到线段树。。。我做腻了）

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

区间修改，区间查询。裸的线段树，本来以为要用二维的线段树，定眼一看发现一共才20行最多，那就建20个线段树就行了。其他的正常计算就行。~~额外补充个地方，在此点有区间重置某个值的情况下向下pushdown，你一定要顺手把下方点的add的懒惰数组清零！！

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 1e6 + 10;
struct *** {
	int sum, maxn, minn;
}c[maxn * 3][21];
int add[maxn * 3][21], chan[maxn * 2][21];
int l[maxn * 3][21], r[maxn * 3][21];
void pushup(int x, int rt) {
	c[rt][x].sum = c[rt << 1][x].sum + c[rt << 1 | 1][x].sum;
	c[rt][x].maxn = max(c[rt << 1][x].maxn, c[rt << 1 | 1][x].maxn);
	c[rt][x].minn = min(c[rt << 1][x].minn, c[rt << 1 | 1][x].minn);
}
void pushdown(int x, int rt, int len) {
	if (chan[rt][x] != -1) {
		c[rt << 1][x].maxn = chan[rt][x];
		c[rt << 1][x].minn = chan[rt][x];
		c[rt << 1][x].sum = (len + 1) / 2 * chan[rt][x];
		add[rt << 1][x] = 0;
		chan[rt << 1][x] = chan[rt][x];
		c[rt << 1 | 1][x].maxn = chan[rt][x];
		c[rt << 1 | 1][x].minn = chan[rt][x];
		c[rt << 1 | 1][x].sum = (len) / 2 * chan[rt][x];
		add[rt << 1 | 1][x] = 0;
		chan[rt << 1 | 1][x] = chan[rt][x];
	}
	if (add[rt][x] != 0) {
		c[rt << 1][x].maxn += add[rt][x];
		c[rt << 1][x].minn += add[rt][x];
		c[rt << 1][x].sum += (len + 1) / 2 * add[rt][x];
		add[rt << 1][x] += add[rt][x];
		c[rt << 1 | 1][x].maxn += add[rt][x];
		c[rt << 1 | 1][x].minn += add[rt][x];
		c[rt << 1 | 1][x].sum += (len) / 2 * add[rt][x];
		add[rt << 1 | 1][x] += add[rt][x];
	}
	chan[rt][x] = -1; add[rt][x] = 0;
}
void build(int x, int l, int r, int rt) {
	add[rt][x] = 0; chan[rt][x] = -1;
	if (l == r) {
		c[rt][x].sum = 0;
		c[rt][x].minn = 0;
		c[rt][x].maxn = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(x, lson);
	build(x, rson);
	pushup(x, rt);
}
void change(int x, int L, int R, int l, int r, int rt, int k) {
	if (L <= l&&r <= R) {
		c[rt][x].sum = (r - l + 1)*k;
		c[rt][x].maxn = c[rt][x].minn = k;
		add[rt][x] = 0; chan[rt][x] = k;
		return;
	}
	int m = (l + r) >> 1; int len = (r - l + 1);
	pushdown(x, rt, len);
	if (L <= m)
		change(x, L, R, lson, k);
	if (R > m)
		change(x, L, R, rson, k);
	pushup(x, rt);
}
void addnum(int x, int L, int R, int l, int r, int rt, int k) {
	if (L <= l&&r <= R) {
		c[rt][x].sum += (r - l + 1)*k;
		c[rt][x].maxn += k; c[rt][x].minn += k;
		add[rt][x] += k;
		return;
	}
	int m = (l + r) >> 1; int len = (r - l + 1);
	pushdown(x, rt, len);
	if (L <= m)
		addnum(x, L, R, lson, k);
	if (R > m)
		addnum(x, L, R, rson, k);
	pushup(x, rt);
}
int query(int x, int L, int R, int l, int r, int rt, int &maxn, int &minn) {
	if (L <= l&&r <= R) {
		maxn = max(maxn, c[rt][x].maxn);
		minn = min(minn, c[rt][x].minn);
		return c[rt][x].sum;
	}
	int m = (l + r) >> 1, len = (r - l + 1);
	int sum = 0;
	pushdown(x, rt, len);
	if (L <= m) {
		sum += query(x, L, R, lson, maxn, minn);
	}
	if (R > m) {
		sum += query(x, L, R, rson, maxn, minn);
	}
	pushup(x, rt);
	return  sum;
}
int main() {
	int n, m, q;
	ios::sync_with_stdio(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		build(i, 1, m, 1);
	while (q--) {
		int a; cin >> a;
		int b, c, d, e, f;
		if (a == 1) {
			cin >> b >> c >> d >> e >> f;
			if (b > d)swap(b, d);
			if (c > e)swap(c, e);
			for (int i = b; i <= d; i++) {
				addnum(i, c, e, 1, m, 1, f);
			}
		}
		else if (a == 2) {
			cin >> b >> c >> d >> e >> f;
			if (b > d)swap(b, d);
			if (c > e)swap(c, e);
			for (int i = b; i <= d; i++) {
				change(i, c, e, 1, m, 1, f);
			}
		}
		else {
			cin >> b >> c >> d >> e;
			if (b > d)swap(b, d);
			if (c > e)swap(c, e);
			int ans = 0, maxn = -1, minn = 2147483647;
			for (int i = b; i <= d; i++) {
				ans += query(i, c, e, 1, m, 1, maxn, minn);
			}
			cout << ans << " " << minn << " " << maxn << "\n";
		}
	}
	return 0;
}