UVA 11992 Fast Matrix Operations（线段树：区间修改）

时间：2023-03-08 18:38:22

题目链接 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);

}

相关文章