UVA 11992 Fast Matrix Operations (二维线段树)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000010

struct node
{
    int mini,maxi,sum;
    int addmark,setmark;
}tree[21][4*N];

int i;

void pushup(int i,int rt)
{
    tree[i][rt].sum = tree[i][2*rt].sum + tree[i][2*rt+1].sum;
    tree[i][rt].mini = min(tree[i][2*rt].mini,tree[i][2*rt+1].mini);
    tree[i][rt].maxi = max(tree[i][2*rt].maxi,tree[i][2*rt+1].maxi);
}

void build(int i,int l,int r,int rt)
{
    tree[i][rt].sum = tree[i][rt].mini = tree[i][rt].maxi = 0;
    tree[i][rt].setmark = -1;
    tree[i][rt].addmark = 0;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(i,l,mid,2*rt);
    build(i,mid+1,r,2*rt+1);
    pushup(i,rt);
}

void pushdown(int i,int l,int r,int rt)
{
    if(tree[i][rt].setmark == -1 && tree[i][rt].addmark == 0)
        return;
    int mid = (l+r)/2;
    if(tree[i][rt].setmark >= 0)
    {
        tree[i][2*rt].sum = tree[i][rt].setmark*(mid-l+1);
        tree[i][2*rt+1].sum = tree[i][rt].setmark*(r-mid);
        tree[i][2*rt].mini = tree[i][2*rt+1].mini = tree[i][rt].setmark;  // 
        tree[i][2*rt].maxi = tree[i][2*rt+1].maxi = tree[i][rt].setmark;  //
        tree[i][2*rt].addmark = tree[i][2*rt+1].addmark = 0;  //
        tree[i][2*rt].setmark = tree[i][2*rt+1].setmark = tree[i][rt].setmark;
        tree[i][rt].setmark = -1;
    }
    if(tree[i][rt].addmark > 0)
    {
        tree[i][2*rt].sum += tree[i][rt].addmark*(mid-l+1);
        tree[i][2*rt+1].sum += tree[i][rt].addmark*(r-mid);
        tree[i][2*rt].maxi += tree[i][rt].addmark;  //
        tree[i][2*rt].mini += tree[i][rt].addmark;
        tree[i][2*rt+1].maxi += tree[i][rt].addmark;
        tree[i][2*rt+1].mini += tree[i][rt].addmark;  //
        tree[i][2*rt].addmark += tree[i][rt].addmark;
        tree[i][2*rt+1].addmark += tree[i][rt].addmark;
        tree[i][rt].addmark = 0;
    }
}

void add(int l,int r,int aa,int bb,int val,int rt)
{
    if(aa>r||bb<l)
        return;
    if(aa<=l&&bb>=r)
    {
        tree[i][rt].addmark += val;
        //tree[i][rt].setmark = -1;
        tree[i][rt].sum += (r-l+1)*val;
        tree[i][rt].maxi += val;
        tree[i][rt].mini += val;
        return;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        add(l,mid,aa,bb,val,2*rt);
    if(bb>mid)
        add(mid+1,r,aa,bb,val,2*rt+1);
    pushup(i,rt);
}

void setval(int l,int r,int aa,int bb,int val,int rt)
{
    if(aa>r||bb<l)
        return;
    if(aa<=l&&bb>=r)
    {
        tree[i][rt].setmark = val;
        tree[i][rt].addmark = 0;
        tree[i][rt].sum = val*(r-l+1);
        tree[i][rt].maxi = tree[i][rt].mini = val;
        return;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        setval(l,mid,aa,bb,val,2*rt);
    if(bb>mid)
        setval(mid+1,r,aa,bb,val,2*rt+1);
    pushup(i,rt);
}

struct node_ans
{
    int sum;
    int mini,maxi;
};

node_ans query(int l,int r,int aa,int bb,int rt)
{
    node_ans res,ka1,ka2;
    if(aa<=l && bb>=r)
    {
        res.sum = tree[i][rt].sum;
        res.maxi = tree[i][rt].maxi;
        res.mini = tree[i][rt].mini;
        return res;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(bb<=mid)
        return query(l,mid,aa,bb,2*rt);
    else if(aa>mid)
        return query(mid+1,r,aa,bb,2*rt+1);
    else
    {
        ka1 = query(l,mid,aa,bb,2*rt);
        ka2 = query(mid+1,r,aa,bb,2*rt+1);
        res.sum = ka1.sum + ka2.sum;
        res.maxi = max(ka1.maxi,ka2.maxi);
        res.mini = min(ka1.mini,ka2.mini);
        return res;
    }
}

int main()
{
    int r,c,m;
    int k,zuo;
    int x1,y1,x2,y2,val;
    int sum,mmax,mmin;
    while(scanf("%d%d%d",&r,&c,&m)!=EOF)
    {
        for(i=1;i<=r;i++)
        {
            build(i,1,c,1);
        }
        for(k=0;k<m;k++)
        {
            scanf("%d",&zuo);
            if(zuo == 1)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(i=x1;i<=x2;i++)
                {
                    add(1,c,y1,y2,val,1);
                }
            }
            else if(zuo == 2)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(i=x1;i<=x2;i++)
                {
                    setval(1,c,y1,y2,val,1);
                }
            }
            else 
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                node_ans la;
                sum = 0;
                mmax = -Mod;
                mmin = Mod;
                for(i=x1;i<=x2;i++)
                {
                    la = query(1,c,y1,y2,1);
                    sum += la.sum;
                    mmax = max(mmax,la.maxi);
                    mmin = min(mmin,la.mini);
                }
                printf("%d %d %d\n",sum,mmin,mmax);
            }
        }
    }
}