题目链接 2015-10-30 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3143
给你一个矩阵，矩阵的每个元素初始值均为0
进行m次操作，操作共有三种类型，分别用1，2，3表示
操作一：子矩阵(x1, y1, x2, y2)的所有元素增加v
操作二：子矩阵(x1, y1, x2, y2)的所有元素设为v
操作三：查询子矩阵(x1, y1, x2, y2)的元素和，最小值和最大值
矩阵只有20行，可以每行建一棵线段树（建议直接转为一维）
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 3000100
#define inf 1000000000
#define LL(x) x<<1
#define RR(x) x<<1|1
using namespace std; typedef long long LL; //variable define struct tree
{
int l, r;
int mi, ma, sum;
int add, set;
}; tree node[maxn];
int row, col, m, ans_mi, ans_ma, ans_sum; //function define void push_down(int x); void push_up(int x); void build_tree(int left, int right, int x); void query(int left, int right, int x); void update_set(int left, int right, int x, int val); void update_add(int left, int right, int x, int val); int main(void)
{
while (scanf("%d %d %d", &row, &col, &m) != EOF)
{
build_tree( , row*col, );
int op, x1, y1, x2, y2, val;
while (m--)
{
scanf("%d", &op);
if (op == )
{
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &val);
for (int i = x1; i <= x2; ++i)
update_add( (i-)*col + y1, (i-)*col + y2, , val);
}
else if (op == )
{
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &val);
for (int i = x1; i <= x2; ++i)
update_set( (i-)*col + y1, (i-)*col + y2, , val);
}
else
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
ans_sum = ;
ans_ma = -inf;
ans_mi = inf;
for (int i = x1; i <= x2; ++i)
query( (i-)*col + y1, (i-)*col + y2, );
//output
printf("%d %d %d\n", ans_sum, ans_mi, ans_ma);
}
}
}
return ;
} void build_tree(int left, int right, int x)
{
node[x].l = left;
node[x].r = right;
node[x].ma = node[x].mi = node[x].sum = ;
node[x].add = ;
node[x].set = -; if (left == right)
return; int lx = LL(x);
int rx = RR(x);
int mid = left + (right - left)/;
build_tree(left, mid, lx);
build_tree(mid + , right, rx);
//push_up(x);
} void push_up(int x)
{
if (node[x].l >= node[x].r)
return; int lx = LL(x);
int rx = RR(x);
node[x].ma = max( node[lx].ma, node[rx].ma);
node[x].mi = min( node[lx].mi, node[rx].mi);
node[x].sum = node[lx].sum + node[rx].sum;
} void push_down(int x)
{
if (node[x].l >= node[x].r)
return;
int lx = LL(x);
int rx = RR(x);
if (node[x].set != -)
{
node[lx].set = node[rx].set = node[x].set;
node[lx].mi = node[rx].mi = node[x].set;
node[lx].ma = node[rx].ma = node[x].set;
node[lx].add = node[rx].add = ;
node[lx].sum = (node[lx].r - node[lx].l + ) * node[x].set;
node[rx].sum = (node[rx].r - node[rx].l + ) * node[x].set;
}
if (node[x].add > )
{
LL tmp = node[x].add;
node[lx].add += tmp;
node[rx].add += tmp;
node[lx].ma += tmp;
node[rx].ma += tmp;
node[lx].mi += tmp;
node[rx].mi += tmp;
node[lx].sum += (tmp * (node[lx].r - node[lx].l + ));
node[rx].sum += (tmp * (node[rx].r - node[rx].l + ));
}
} void update_set(int left, int right, int x, int val)
{
if (node[x].l == left && node[x].r == right)
{
node[x].set = val;
node[x].ma = node[x].mi = val;
node[x].sum = (right - left + ) * val;
node[x].add = ;
return;
}
push_down(x);
node[x].set = -;
node[x].add = ;
int lx = LL(x);
int rx = RR(x);
int mid = node[x].l + (node[x].r - node[x].l)/;
if (right <= mid)
update_set(left, right, lx, val);
else if (left > mid)
update_set(left, right, rx, val);
else
{
update_set(left, mid, lx, val);
update_set(mid + , right, rx, val);
}
push_up( x);
} void update_add(int left, int right, int x, int val)
{
if (node[x].l == left && node[x].r == right)
{
node[x].add += val;
node[x].ma += val;
node[x].mi += val;
node[x].sum += (node[x].r - node[x].l + ) * val;
return;
}
push_down( x);
node[x].set = -;
node[x].add = ;
int lx = LL(x);
int rx = RR(x);
int mid = node[x].l + (node[x].r - node[x].l)/; if (right <= mid)
update_add(left, right, lx, val);
else if (left > mid)
update_add(left, right, rx, val);
else
{
update_add(left, mid, lx, val);
update_add(mid + , right, rx, val);
}
push_up(x);
} void query(int left, int right, int x)
{
if (node[x].l == left && node[x].r == right)
{
ans_sum += node[x].sum;
ans_ma = max( ans_ma, node[x].ma);
ans_mi = min( ans_mi, node[x].mi);
return;
}
push_down(x);
node[x].set = -;
node[x].add = ;
int mid = node[x].l + (node[x].r - node[x].l)/;
int lx = LL(x);
int rx = RR(x);
if (right <= mid)
query(left, right, lx);
else if (left > mid)
query(left, right, rx);
else
{
query(left, mid, lx);
query(mid + , right, rx);
}
push_up(x);
}