uva 11992 为矩阵更新查询段树

http://uva.onlinejudge.org/index.php?

option=com_onlinejudge&Itemid=8&page=show_problem&problem=3143

矩阵变成一行，然后计算位置。lrj给了线段树数组做法 可是我做的线段树空间过大，直接爆掉，所以换方法了

主要还是測试自己的线段树区间更新的模板

各种RE+WA之后AC，，，，。

做的时候出现的几个错误：

1、行和列弄错

2、build初始化的时候，mmin mmax 都初始化为0才对

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define lson(i) l , mid , (i)*2

#define rson(i) mid + 1 , r , ((i)*2 +1)

#define ll rt*2

#define rr (rt*2+1)

const int INFMIN = 0xffffffff;

const int INFMAX = 1000000009;//0x80000000;

const int MAXN = 30001000;

struct Node{

    int l,r;

    int mmax,mmin,sum,add,s;/*s去标记是不是被set*/

};

Node nodes[MAXN];

    int mmax,mmin,sum;

    void PushUp(int rt)

    {

        nodes[rt].mmax = max(nodes[ll].mmax,nodes[rr].mmax);

        nodes[rt].mmin = min(nodes[ll].mmin,nodes[rr].mmin);

        nodes[rt].sum = nodes[ll].sum + nodes[rr].sum;

    }

    void PushDown(int rt)

    {

        //if(nodes[rt].add && flag == 1)

        if(nodes[rt].add)

        {

            nodes[ll].add += nodes[rt].add;

            nodes[ll].mmin += nodes[rt].add;

            nodes[ll].mmax += nodes[rt].add;

            nodes[rr].add += nodes[rt].add;

            nodes[rr].mmin += nodes[rt].add;

            nodes[rr].mmax += nodes[rt].add;

            nodes[ll].sum += nodes[rt].add*(nodes[ll].r-nodes[ll].l+1);

            nodes[rr].sum += nodes[rt].add*(nodes[rr].r-nodes[rr].l+1);

            nodes[rt].add = 0;

        }

        //if(nodes[rt].s && flag == 2)

        if(nodes[rt].s)

        {

            nodes[ll].s = nodes[rr].s=nodes[rt].s;

            nodes[ll].mmin = nodes[ll].mmax = nodes[rr].mmax = nodes[rr].mmin = nodes[rt].mmax;

            nodes[ll].sum = nodes[rt].mmin*(nodes[ll].r-nodes[ll].l+1);

            nodes[rr].sum = nodes[rt].mmin*(nodes[rr].r-nodes[rr].l+1);

            nodes[ll].add = nodes[rr].add = 0;//////////////

            nodes[rt].s=0;

        }

    }

    void Build(int l,int r,int rt)

    {

        nodes[rt].l=l;

        nodes[rt].r=r;

        nodes[rt].add =0;

        nodes[rt].s=0;

        nodes[rt].sum =0;

        nodes[rt].mmin=0;

        nodes[rt].mmax=0;

        if(l == r)

        {

            //nodes[rt].mmin = nodes[rt].mmax = nodes[rt].sum =a[l];

            nodes[rt].mmin = nodes[rt].mmax = nodes[rt].sum =0;////////////////

            return ;

        }

        int mid = (nodes[rt].l+nodes[rt].r)/2;

        Build(lson(rt));

        Build(rson(rt));

        //PushUp(rt);

    }

    void Update(int l,int r,int add,int rt,int flag)

    {

/////////////////////////////////////////////////////////////////

//printf("rt=%d l=%d r=%d add=%d flag =%d nodes[rt].l=%d nodes[rt].r=%d\n",rt,l,r,add,flag,nodes[rt].l,nodes[rt].r);

        if(l<=nodes[rt].l && nodes[rt].r<=r)

        {

            if(flag == 1)/*increase*/

            {

                nodes[rt].mmax += add;

                nodes[rt].mmin += add;

                nodes[rt].add += add;

                nodes[rt].sum += add*(nodes[rt].r-nodes[rt].l+1);

            }

            else

            {

                nodes[rt].mmax = add;

                nodes[rt].mmin = add;

                nodes[rt].add=0;

                nodes[rt].s=1;

                nodes[rt].sum = add*(nodes[rt].r-nodes[rt].l+1);

            }

            return;

        }

        PushDown(rt);

        int mid = (nodes[rt].l+nodes[rt].r)/2;

        if(l<=mid)Update(l,r,add,ll,flag);

        if(r>mid)Update(l,r,add,rr,flag);

        PushUp(rt);

    }

    void Query(int l,int r,int rt)/*1表示mmin 2--mmax 3-sum*/

    {

    /////////////////////////////////////////////////////////////////

//printf("rt=%d l=%d r=%d  nodes[rt].l=%d nodes[rt].r=%d\n",rt,l,r,nodes[rt].l,nodes[rt].r);

 ///////////////////////////////////////////////////////////////////////////

        if(l<=nodes[rt].l && nodes[rt].r<=r)

        {

            mmin = min(mmin,nodes[rt].mmin);

            mmax = max(mmax,nodes[rt].mmax);

            sum += nodes[rt].sum;

            return ;

        }

        PushDown(rt);

        int mid = (nodes[rt].l+nodes[rt].r)/2;

        if(l<=mid)Query(l,r,ll);

        if(r>mid)Query(l,r,rr);

        PushUp(rt);

    }

    void clr()/*每次查询之前使用*/

    {

        sum =0;

        mmin=INFMAX;

        mmax=INFMIN;

    }

int main()

{

    //freopen("uva11992.txt","r",stdin);

    int r,c,m,v,flag,x1,y1,x2,y2;

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

    {

        Build(1,r*c,1);

        while(m--)

        {

            scanf("%d%d%d%d%d",&flag,&x1,&y1,&x2,&y2);

            if(flag<3)

            {

                scanf("%d",&v);

                for(int i=x1;i<=x2;i++)/*此处注意*/

                {

///////////////////////////////////////////////////////////////

//printf("i=%d\n",i);

                    Update(y1+(i-1)*c,y2+(i-1)*c,v,1,flag);

                }

            }

            else

            {

                int anssum=0,ansmin=INFMAX,ansmax=INFMIN;

                for(int i=x1;i<=x2;i++)

                {

                    clr();

                    Query(y1+(i-1)*c,y2+(i-1)*c,1);

                    ////////////////////////

                   // printf("**min=%d\n",mmin);

                    /////////////////

                    anssum+=sum;

                    ansmax=max(ansmax,mmax);

                    ansmin=min(ansmin,mmin);

                }

                printf("%d %d %d\n",anssum,ansmin,ansmax);

            }

        }

    }

    return 0;

}