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;
}