题意:训练指南P207

分析:因为矩阵不超过20行,所以可以建20条线段的线段树,支持两个区间更新以及区间查询.

#include 
     
      using namespace std;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 20 + 5;const int M = 5e4 + 5;struct Segment_Tree	{	struct Node	{		int sum, mx, mn, add, setv;	}node[M<<2];	void _max(int &a, int b)	{		if (a < b)	a = b;	}	void _min(int &a, int b)	{		if (a > b)	a = b;	}	void push_up(int o)	{		node[o].sum = node[o<<1].sum + node[o<<1|1].sum;		node[o].mx = max (node[o<<1].mx, node[o<<1|1].mx);		node[o].mn = min (node[o<<1].mn, node[o<<1|1].mn);	}	void push_down(int l, int r, int o)	{		int len = r - l + 1;		if (node[o].setv != -1 && l < r)	{					//先set,然后再add			node[o<<1].setv = node[o<<1|1].setv = node[o].setv;			node[o<<1].add = node[o<<1|1].add = 0;				//很重要的地方,有set的清除add,意思是set前的add都不要了			node[o<<1].sum = node[o].setv * (len - (len >> 1));			node[o<<1].mx = node[o<<1].mn = node[o].setv;			node[o<<1|1].sum = node[o].setv * (len >> 1);			node[o<<1|1].mx = node[o<<1|1].mn = node[o].setv;			node[o].setv = -1;		}		if (node[o].add != 0 && l < r)	{			node[o<<1].add += node[o].add;	node[o<<1|1].add += node[o].add;			node[o<<1].sum += node[o].add * (len - (len >> 1));			node[o<<1].mx += node[o].add;	node[o<<1].mn += node[o].add;			node[o<<1|1].sum += node[o].add * (len >> 1);			node[o<<1|1].mx += node[o].add;	node[o<<1|1].mn += node[o].add;			node[o].add = 0;		}	}	void build(int l, int r, int o)	{		node[o].add = 0;	node[o].setv = -1;		if (l == r)	{			node[o].sum = 0;	node[o].mx = 0;	node[o].mn = 0;			return ;		}		int mid = l + r >> 1;		build (lson);	build (rson);		push_up (o);	}	void updata(int ql, int qr, int op, int c, int l, int r, int o)	{		if (ql <= l && r <= qr)	{			if (op == 1)	{				node[o].sum += c * (r - l + 1);	node[o].mx += c;	node[o].mn += c;				node[o].add += c;	return ;			}			else if (op == 2)	{				node[o].sum = c * (r - l + 1);	node[o].mx = node[o].mn = c;				node[o].add = 0;				node[o].setv = c;	return ;			}		}		push_down (l, r, o);		int mid = l + r >> 1;		if (ql <= mid)	updata (ql, qr, op, c, lson);		if (qr > mid)	updata (ql, qr, op, c, rson);		push_up (o);	}	void query(int ql, int qr, int &_sum, int &_mn, int &_mx, int l, int r, int o)	{		if (ql <= l && r <= qr)	{			_sum += node[o].sum;			_max (_mx, node[o].mx);			_min (_mn, node[o].mn);			return ;		}		push_down (l, r, o);		int mid = l + r >> 1;		if (ql <= mid)	query (ql, qr, _sum, _mn, _mx, lson);		if (qr > mid)	query (ql, qr, _sum, _mn, _mx, rson);	}}st[N];int n, m, q;int main(void)	{	while (scanf ("%d%d%d", &n, &m, &q) == 3)	{		for (int i=1; i<=n; ++i)	{			st[i].build (1, m, 1);		}		int x1, y1, x2, y2, v, op;		while (q--)	{			scanf ("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);			if (op <= 2)	{				scanf ("%d", &v);				for (int i=x1; i<=x2; ++i)	{					st[i].updata (y1, y2, op, v, 1, m, 1);				}			}			else	{				int sum = 0, mx = 0, mn = INF;				for (int i=x1; i<=x2; ++i)	{					st[i].query (y1, y2, sum, mn, mx, 1, m, 1);				}				printf ("%d %d %d\n", sum, mn, mx);			}		}	}	return 0;}