uva 1401 Fast Matrix Operations 高速矩阵操作 （线段树 区间修改和查询）

uva 1401 Fast Matrix Operations 快速矩阵操作 （线段树 区间修改和查询）

题意：给一个r行c列的全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）的元素和、最小值、最大值。

子矩阵（x1 y1 x2 y2）是指满足 x1 <= x <= x2, y1 <= y <= y2的所有元素（x,y）。

矩阵不超过20行，矩阵总元素可多达10^6个。

思路：矩阵行数不超过20行，元素总数可达10^6 可以想到每行建一个线段树。

两个操作 add和set ,所以需要两个标记addv和setv。

规定同时有两个标记时 ， 表示先执行set再执行add。

在update函数的递归边界上 对于set操作，需要将该节点addv标记清除，但对于add操作，不清除setv标记；

在maintain函数中要先考虑setv，再考虑addv；

在query函数中，需要综合考虑setv和addv的影响；

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int r,c,m;
int op,x1,y1,x2,y2,v,x;
int _sum, _min, _max;

const int maxnode = 1<<17;

struct IntervalTree{
    int addv[maxnode],setv[maxnode],sumv[maxnode],minv[maxnode],maxv[maxnode];

    void maintain(int o, int L, int R){
        int lc = o*2, rc = o*2+1;
        if(L < R){
            sumv[o] = sumv[lc] + sumv[rc];
            maxv[o] = max(maxv[lc], maxv[rc]);
            minv[o] = min(minv[lc], minv[rc]);
        }
        if(setv[o] >= 0){
            minv[o] = maxv[o] = setv[o];
            sumv[o] = setv[o] * (R-L+1);
        }
        if(addv[o]){
            minv[o] += addv[o];
            maxv[o] += addv[o];
            sumv[o] += addv[o] * (R-L+1);
        }
    }
    void pushdown(int o){
        int lc = o*2, rc = o*2+1;
        if(setv[o] >= 0){
            setv[lc] = setv[rc] = setv[o];
            addv[lc] = addv[rc] = 0;
            setv[o] = -1;
        }
        if(addv[o]){
            addv[lc] += addv[o]; /// wrong answer
            addv[rc] += addv[o]; /// wrong answer
            addv[o] = 0;
        }
    }
    void update(int o, int L, int R){
        int lc = o*2, rc = o*2+1;
        if(y1 <= L && y2 >= R){
            if(op == 2){
                setv[o] = v;
                addv[o] = 0;
            }
            else{
                addv[o] += v;
            }
        }
        else{
            pushdown(o);
            int M = L + (R-L)/2;
            if(y1 <= M) update(lc, L, M);
            else maintain(lc, L, M);
            if(y2 > M) update(rc, M+1, R);
            else maintain(rc, M+1, R);
        }
        maintain(o, L, R); /// wrong answer;
    }
    void query(int o, int L, int R, int add){
        if(setv[o] >= 0){
            int v = setv[o] + addv[o] + add;
            _sum += v * (min(R, y2)-max(L, y1)+1); /// wrong answer
            _max = max(_max, v);
            _min = min(_min, v);
        }
        else if(y1 <= L && y2 >= R){
            _sum += sumv[o] + add*(R-L+1); /// wrong answer
            _max = max(_max, maxv[o]+add); /// wrong answer
            _min = min(_min, minv[o]+add); /// wrong answer
        }
        else{
            int lc = o*2, rc = o*2+1;
            int M = L + (R-L)/2;
            if(y1 <= M) query(lc, L, M, add+addv[o]);
            if(y2 > M) query(rc, M+1, R, add+addv[o]);
        }
    }
}tree[25];

const int INF = 0x3f3f3f3f;

int main(){
    while(scanf("%d%d%d",&r,&c,&m) != EOF){

        memset(tree, 0, sizeof(tree));
        for(int i = 0; i <= r; i++){
            memset(tree[i].setv, -1, sizeof(tree[i].setv));
            tree[i].setv[1] = 0;/// wrong answer point
        }
        while(m--){
            scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
            if(op < 3){
                scanf("%d",&v);
                for(int x = x1; x <= x2; x++){
                    tree[x].update(1, 1, c);
                }
            }
            else{
                _max = -INF;_min = INF;_sum = 0;
                for(int x = x1; x <= x2; x++){
                    tree[x].query(1, 1, c, 0);
                }
                printf("%d %d %d\n",_sum, _min, _max);
            }
        }
    }

    return 0;
}

上面代码中的 wrong answer 处，是在敲线段树时犯错的地方。第一次做线段树的题目，标记出来提醒自己。

main函数中先对线段树数组 tree[]数组 清零~

另外将所有的setv[]点设成-1值，表示该节点并没有 被修改过；

但是！但是不要忘记紧接着写上：tree[i].setv[1] = 0; 这个不可少，因为它的意思是，将本行（线段树中）所有元素的值设为零，即相当于初始化~ 没写这个wrong了两发T_T。。。