本文主要是介绍Fast Matrix Operations （UVA - 11992，二维线段树 + 简单应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
UVA-11992
二.题目大意：
有一个 r × c 大小的矩阵，最多有 个元素，r ≤ 20.
矩阵中元素的初始值均为 0.
现有三种操作
① 1 x1 y1 x2 y2 v ：将 (x1, y1) 到 (x2, y2) 之间的元素都加上值 v.
② 2 x1 y1 x2 y2 v：将 (x1, y1) 到 (x2, y2) 之间的元素都置为值 v.
③ 3 x1 y1 x2 y2 ：查询 (x1, y1) 到 (x2, y2) 之间的元素的 和、最大值、最小值，并将其输出.
操作总数 m ≤ .
三.分析：
这三种操作当然是线段树的基本操作啦.
由于 r ≤ 20，所以建造 r 个线段树即可.
把 左右区间、最小值、最大值、和、懒惰标记、set 值封装在结构体了就可以了.
这里注意一点：
在函数 down 中 set 和 add 的顺序
假设操作时先进行了 set 后进行了 add，那么这里肯定是要先 set 再 add 的.
相反，由于在 set 时，已经将 tree[row][k].add = 0，所以此时也是可以先进行 set的.
四.代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;const int M = (int)1e6 + 10;
const int inf = 0x3f3f3f3f;
struct node1
{int l, r;int sum, add;int Max, Min;int Set;
}tree[21][M * 3];struct node2
{int sum;int Min;int Max;
}tnode;void build(int k, int l, int r, int row)
{tree[row][k].l = l;tree[row][k].r = r;tree[row][k].sum = 0;tree[row][k].add = 0;tree[row][k].Max = 0;tree[row][k].Min = 0;tree[row][k].Set = -1;if(l == r)return;int m = (l + r) / 2;build(k * 2, l, m, row);build(k * 2 + 1, m + 1, r, row);
}void down(int row, int k)
{int lk = 2 * k;int rk = 2 * k + 1;if(~tree[row][k].Set){tree[row][lk].Set = tree[row][rk].Set = tree[row][k].Set;tree[row][lk].add = tree[row][rk].add = 0;tree[row][k].Set = -1;tree[row][lk].sum = (tree[row][lk].r - tree[row][lk].l + 1) * tree[row][lk].Set;tree[row][rk].sum = (tree[row][rk].r - tree[row][rk].l + 1) * tree[row][rk].Set;tree[row][lk].Max = tree[row][lk].Min = tree[row][lk].Set;tree[row][rk].Max = tree[row][rk].Min = tree[row][rk].Set;}if(tree[row][k].add > 0){tree[row][lk].add += tree[row][k].add;tree[row][rk].add += tree[row][k].add;tree[row][lk].sum += (tree[row][lk].r - tree[row][lk].l + 1) * tree[row][k].add;tree[row][rk].sum += (tree[row][rk].r - tree[row][rk].l + 1) * tree[row][k].add;tree[row][lk].Min += tree[row][k].add;tree[row][lk].Max += tree[row][k].add;tree[row][rk].Min += tree[row][k].add;tree[row][rk].Max += tree[row][k].add;tree[row][k].add = 0;}
}void add(int k, int y1, int y2, int v, int row)
{if(tree[row][k].l >= y1 && tree[row][k].r <= y2){tree[row][k].sum += (tree[row][k].r - tree[row][k].l + 1) * v;tree[row][k].add += v;tree[row][k].Min += v;tree[row][k].Max += v;return;}if(tree[row][k].add || ~tree[row][k].Set)down(row, k);int m = (tree[row][k].l + tree[row][k].r) / 2;if(y1 <= m)add(k * 2, y1, y2, v, row);if(m < y2)add(k * 2 + 1, y1, y2, v, row);tree[row][k].sum = tree[row][k * 2].sum + tree[row][k * 2 + 1].sum;tree[row][k].Max = max(tree[row][k * 2].Max, tree[row][k * 2 + 1].Max);tree[row][k].Min = min(tree[row][k * 2].Min, tree[row][k * 2 + 1].Min);
}void Set(int k, int y1, int y2, int v, int row)
{if(tree[row][k].l >= y1 && tree[row][k].r <= y2){tree[row][k].sum = (tree[row][k].r - tree[row][k].l + 1) * v;tree[row][k].add = 0;tree[row][k].Set = v;tree[row][k].Min = v;tree[row][k].Max = v;return;}if(tree[row][k].add || ~tree[row][k].Set)down(row, k);int m = (tree[row][k].l + tree[row][k].r) / 2;if(y1 <= m)Set(k * 2, y1, y2, v, row);if(m < y2)Set(k * 2 + 1, y1, y2, v, row);tree[row][k].sum = tree[row][k * 2].sum + tree[row][k * 2 + 1].sum;tree[row][k].Max = max(tree[row][k * 2].Max, tree[row][k * 2 + 1].Max);tree[row][k].Min = min(tree[row][k * 2].Min, tree[row][k * 2 + 1].Min);
}void query(int k, int y1, int y2, int row)
{if(tree[row][k].l >= y1 && tree[row][k].r <= y2){tnode.sum += tree[row][k].sum;tnode.Max = max(tnode.Max, tree[row][k].Max);tnode.Min = min(tnode.Min, tree[row][k].Min);return;}if(tree[row][k].add || ~tree[row][k].Set)down(row, k);int m = (tree[row][k].l + tree[row][k].r) / 2;if(y1 <= m)query(k * 2, y1, y2, row);if(m < y2)query(k * 2 + 1, y1, y2, row);
}int main()
{int r, c, m;while(~scanf("%d %d %d", &r, &c, &m)){for(int i = 1; i <= r; ++i)build(1, 1, c, i);while(m--){int t, x1, y1, x2, y2;scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);if(t == 1){int v;scanf("%d", &v);for(int i = x1; i <= x2; ++i)add(1, y1, y2, v, i);}else if(t == 2){int v;scanf("%d", &v);for(int i = x1; i <= x2; ++i)Set(1, y1, y2, v, i);}else if(t == 3){int sum = 0;int Max = -inf;int Min = inf;for(int i = x1; i <= x2; ++i){tnode.sum = 0;tnode.Max = -inf;tnode.Min = inf;query(1, y1, y2, i);sum += tnode.sum;Max = max(Max, tnode.Max);Min = min(Min, tnode.Min);}printf("%d %d %d\n", sum, Min, Max);}}}return 0;
}这篇关于Fast Matrix Operations （UVA - 11992，二维线段树 + 简单应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
