练基本功 成段更新求2维区间最大值最小值以及和 把某个区间置为v 把某个区间都加上v
难点是set与add的先后顺序的处理
如果先做add在做set那么add是没用的 所以做set时将add置为0
当add不为0 并且 set不为0 那么set肯定在add前面（如果在后面 那么add就置为0了）所以这种情况先做set
当add为0 set不为0 肯定要做set
当add不为0 set为0 做add
都为0（做他干嘛）
所以 按照先set 在add的顺序满足上诉实况
不知小弟理解是否有错
望各位大哥不吝赐教
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 1000010;
struct node
{
int l;
int r;
int max_val;
int min_val;
int sum;
int addv;
int setv;
};
node a[22][maxn<<2], p;
void pushup(int i, int rt)
{
a[i][rt].sum = a[i][rt<<1].sum + a[i][rt<<1|1].sum;
a[i][rt].max_val = max(a[i][rt<<1].max_val, a[i][rt<<1|1].max_val);
a[i][rt].min_val = min(a[i][rt<<1].min_val, a[i][rt<<1|1].min_val);
}
void pushdown(int i, int rt)
{
int k = a[i][rt].r - a[i][rt].l + 1;
if(a[i][rt].setv != -1)
{
a[i][rt<<1].setv = a[i][rt<<1|1].setv = a[i][rt].setv;
a[i][rt<<1].min_val = a[i][rt<<1|1].min_val = a[i][rt].setv;
a[i][rt<<1].max_val = a[i][rt<<1|1].max_val = a[i][rt].setv;
a[i][rt<<1].sum = a[i][rt].setv * (k - (k >> 1));
a[i][rt<<1|1].sum = a[i][rt].setv * (k >> 1);
a[i][rt].setv = -1;
a[i][rt<<1].addv = 0;
a[i][rt<<1|1].addv = 0;
}
if(a[i][rt].addv)
{
a[i][rt<<1].addv += a[i][rt].addv;
a[i][rt<<1].max_val += a[i][rt].addv;
a[i][rt<<1].min_val += a[i][rt].addv;
a[i][rt<<1].sum += a[i][rt].addv * (k - (k >> 1));
a[i][rt<<1|1].addv += a[i][rt].addv;
a[i][rt<<1|1].max_val += a[i][rt].addv;
a[i][rt<<1|1].min_val += a[i][rt].addv;
a[i][rt<<1|1].sum += a[i][rt].addv * (k >> 1);
a[i][rt].addv = 0;
}
}
void build(int i, int l, int r, int rt)
{
//printf("%d %d %d %d\n", i, l, r, rt);
a[i][rt].sum = 0;
a[i][rt].max_val = 0;
a[i][rt].min_val = 0;
a[i][rt].addv = 0;
a[i][rt].setv = -1;
a[i][rt].l = l;
a[i][rt].r = r;
if(l == r)
return;
int m = (l + r) >> 1;
build(i, l, m, rt<<1);
build(i, m+1, r, rt<<1|1);
}
void update(int i, int x, int y, int rt, int v, int key)
{
if(a[i][rt].l == x && a[i][rt].r == y)
{
if(key == 1)
{
a[i][rt].addv += v;
a[i][rt].sum += (y-x+1)*v;
a[i][rt].max_val += v;
a[i][rt].min_val += v;
}
else
{
a[i][rt].setv = v;
a[i][rt].sum = (y-x+1)*v;
a[i][rt].max_val = v;
a[i][rt].min_val = v;
a[i][rt].addv = 0;
}
return;
}
//if(a[i][rt].l == a[i][rt].r)
// return;
pushdown(i, rt);
int m = (a[i][rt].l + a[i][rt].r) >> 1;
if(y <= m)
update(i, x, y, rt<<1, v, key);
else if(x > m)
update(i, x, y, rt<<1|1, v, key);
else
{
update(i, x, m, rt<<1, v, key);
update(i, m+1, y, rt<<1|1, v, key);
}
pushup(i, rt);
}
void query(int i, int x, int y, int rt)
{
if(a[i][rt].l == x && a[i][rt].r == y)
{
p.sum += a[i][rt].sum;
p.min_val = min(p.min_val, a[i][rt].min_val);
p.max_val = max(p.max_val, a[i][rt].max_val);
return;
}
pushdown(i, rt);
int m = (a[i][rt].l + a[i][rt].r) >> 1;
if(y <= m)
query(i, x, y, rt<<1);
else if(x > m)
query(i, x, y, rt<<1|1);
else
{
query(i, x, m, rt<<1);
query(i, m+1, y, rt<<1|1);
}
pushup(i, rt);
}
int main()
{
int n, m, q;
while(scanf("%d %d %d", &n, &m, &q) != EOF)
{
for(int i = 1; i <= n; i++)
build(i, 1, m, 1);
//puts("s");
/*for(int i = 1; i <= n; ++i)
for(int j = m << 2; j >= 0; -- j)
a[i][j].max_val = a[i][j].min_val = a[i][j].addv = a[i][j].sum = 0, a[i][j].setv = -1;*/
while(q--)
{
int k;
scanf("%d", &k);
if(k == 1)
{
int x1, y1, x2, y2, v;
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
for(int i = x1; i <= x2; i++)
update(i, y1, y2, 1, v, 1);
}
else if(k == 2)
{
int x1, y1, x2, y2, v;
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
for(int i = x1; i <= x2; i++)
update(i, y1, y2, 1, v, 2);
}
else
{
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
p.sum = 0;
p.max_val = 0;
p.min_val = 999999999;
for(int i = x1; i <= x2; i++)
query(i, y1, y2, 1);
printf("%d %d %d\n", p.sum, p.min_val, p.max_val);
}
}
}
return 0;
}