首页 > 代码库 > uva 11992 - Fast Matrix Operations(线段树)
uva 11992 - Fast Matrix Operations(线段树)
题目链接:uva 11992 - Fast Matrix Operations
题目大意:给定一个R?C的矩阵,初始状态每个位置均为0, 然后进行Q次操作
- 1,x1,y1,x2,y2,v:将所有(x,y)满足(x1≤x≤x2,y1≤y≤y2)的点加上v
- 2,x1,y1,x2,y2,v:将所有(x,y)满足(x1≤x≤x2,y1≤y≤y2)的点变成v
- 3,x1,y1,x2,y2:求所有(x,y)满足(x1≤x≤x2,y1≤y≤y2)的点的和
解题思路:因为横坐标不会超过20, 所以建立一个一维的线段树即可处理,vset表示修改值,vadd表示添加值,pushdown遵循先set后add,每次set一个节点后要将add清零
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
const int maxn = 1e6+6;
const int INF = 1<<30;
struct Item {
int sum_val, max_val, min_val;
Item (int sum_val = 0, int max_val = 0, int min_val = 0) {
this->set(sum_val, max_val, min_val);
}
void set (int sum_val, int max_val, int min_val) {
this->sum_val = sum_val;
this->max_val = max_val;
this->min_val = min_val;
}
};
struct Node {
int l, r;
Item v;
int vset, vadd;
void set (int l, int r, int vset, int vadd) {
this->l = l;
this->r = r;
this->vset = vset;
this->vadd = vadd;
}
} node[maxn*4];
int R, C, Q;
inline Item get_item (Item a, Item b) {
return Item(a.sum_val + b.sum_val, max(a.max_val, b.max_val), min(a.min_val, b.min_val));
}
inline void add_node (int u, int val) {
node[u].vadd += val;
node[u].v.sum_val += (node[u].r - node[u].l + 1) * val;
node[u].v.max_val += val;
node[u].v.min_val += val;
}
inline void set_node (int u, int val) {
node[u].vadd = 0; // clear vadd after set value;
node[u].vset = val;
node[u].v.sum_val = (node[u].r - node[u].l + 1) * val;
node[u].v.max_val = val;
node[u].v.min_val = val;
}
void pushup(int u) {
node[u].set(node[lson(u)].l, node[rson(u)].r, -1, 0);
node[u].v = get_item(node[lson(u)].v, node[rson(u)].v);
}
void pushdown(int u) {
if (node[u].vset >= 0) {
set_node(lson(u), node[u].vset);
set_node(rson(u), node[u].vset);
node[u].vset = -1;
}
if (node[u].vadd) {
add_node(lson(u), node[u].vadd);
add_node(rson(u), node[u].vadd);
node[u].vadd = 0;
}
}
void build_segTree (int u, int l, int r) {
if (l == r) {
node[u].set(l, r, -1, 0);
node[u].v.set(0, 0, 0);
return;
}
int mid = (l + r) / 2;
build_segTree(lson(u), l, mid);
build_segTree(rson(u), mid + 1, r);
pushup(u);
}
void add_segTree (int u, int l, int r, int val) {
if (l <= node[u].l && node[u].r <= r) {
add_node(u, val);
return;
}
pushdown(u);
int mid = (node[u].l + node[u].r) / 2;
if (l <= mid)
add_segTree(lson(u), l, r, val);
if (r > mid)
add_segTree(rson(u), l, r, val);
pushup(u);
}
void set_segTree (int u, int l, int r, int val) {
if (l <= node[u].l && node[u].r <= r) {
set_node(u, val);
return;
}
pushdown(u);
int mid = (node[u].l + node[u].r) / 2;
if (l <= mid)
set_segTree(lson(u), l, r, val);
if (r > mid)
set_segTree(rson(u), l, r, val);
pushup(u);
}
Item query_segTree (int u, int l, int r) {
if (l <= node[u].l && node[u].r <= r)
return node[u].v;
pushdown(u);
Item ret(0, -INF, INF);
int mid = (node[u].l + node[u].r) / 2;
if (l <= mid)
ret = get_item(ret, query_segTree(lson(u), l, r));
if (r > mid)
ret = get_item(ret, query_segTree(rson(u), l, r));
return ret;
}
int main () {
while (scanf("%d%d%d", &R, &C, &Q) == 3) {
build_segTree(1, 1, R * C);
int sign, x1, y1, x2, y2, v;
for (int i = 0; i < Q; i++) {
scanf("%d", &sign);
if (sign != 3) {
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
for (int j = x1 - 1; j < x2; j++) {
if (sign == 1)
add_segTree(1, j * C + y1, j * C + y2, v);
else
set_segTree(1, j * C + y1, j * C + y2, v);
}
} else {
Item ans(0, -INF, INF);
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
for (int j = x1 - 1; j < x2; j++) {
Item tmp = query_segTree(1, j * C + y1, j * C + y2);
ans = get_item(ans, tmp);
}
printf("%d %d %d\n", ans.sum_val, ans.min_val, ans.max_val);
}
}
}
return 0;
}
uva 11992 - Fast Matrix Operations(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。