题意:训练指南P207
分析:因为矩阵不超过20行,所以可以建20条线段的线段树,支持两个区间更新以及区间查询.
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef 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;
}