问题描述

线段树 uva11992 求大神帮看看，实在不知道错在哪里。。。。。

特别是，Query函数这个函数，我实在是晕的很。。。。。

#include
#include
#include
#include
using namespace std;

#define MAX 3000100
const int inf=1000000009;
const int MAXN = 1000010;
struct Node{
int L,R;
int minv,maxv,sumv;
int addv,setv;
// Node(int l,int r, int x=0,int y=0,int z=0,int w=0,int v=-1):L(l),R(r),minv(x),maxv(y),sumv(z),addv(w),setv(v){}
}a[MAXN*5];

int r,c,m;
int _max[22], _min[22], _sum[22];

void build(int l,int r,int index)
{
a[index].L = l;
a[index].R = r;
a[index].minv=a[index].maxv=a[index].sumv=0;
a[index].addv=0;
a[index].setv=-1;
if(l==r)
return;
int mid = l+(r-l)/2;
build(l,mid,index<<1);
build(mid+1,r,index<<1|1);
}

void maintain(int o)
{
if(a[o].R>a[o].L)
{
a[o].sumv = a[o<<1].sumv + a[o<<1|1].sumv;
a[o].maxv = max(a[o<<1].maxv,a[o<<1|1].maxv);
a[o].minv = min(a[o<<1].minv,a[o<<1|1].minv);
}

}

void pushdown(int o)
{
//将对min,max和sum的修改移到了update函数中
int lc=o<<1,rc=o<<1|1;
if(a[o].setv!=-1)
{
if(a[o].L != a[o].R)
{
a[lc].setv = a[rc].setv = a[o].setv;

        a[lc].addv = a[rc].addv = 0;     //关注
        a[lc].maxv = a[lc].setv;
        a[lc].minv = a[lc].setv;
        a[lc].sumv = a[lc].setv*(a[lc].R-a[lc].L+1);
        a[rc].maxv = a[rc].setv;
        a[rc].minv = a[rc].setv;
        a[rc].sumv = a[rc].setv*(a[rc].R-a[rc].L+1);
    }
    a[o].setv = -1;
}
if(a[o].addv>0)
{
    if(a[o].L != a[o].R)
    {
        int tmpa=a[o].addv;
        a[lc].addv += tmpa;a[rc].addv += tmpa;      //关注，是加上tmpa
        a[lc].minv += tmpa;
        a[lc].maxv += tmpa;
        a[lc].sumv += tmpa*(a[lc].R-a[lc].L+1);
        a[rc].minv += tmpa;
        a[rc].maxv += tmpa;
        a[rc].sumv += tmpa*(a[rc].R-a[rc].L+1);
    }
    a[o].addv = 0;
}

}

void UpdateAdd(int l,int r,int val,int o)
{
int lc=o<
if(l=a[o].R)
{
a[o].addv += val;
// a[o].setv += val;
a[o].minv += a[o].addv;
a[o].maxv += a[o].addv;
a[o].sumv += a[o].addv*(a[o].R-a[o].L+1);
}
else{
pushdown(o);
int M = a[o].L+(a[o].R-a[o].L)/2;
if(l<=M)UpdateAdd(l,r,val,o<
if(r>M)UpdateAdd(l,r,val,o<<1|1);
maintain(o);
}

}

void UpdateSet(int l,int r,int val,int o)
{
int lc=o<<1 , rc=o<<1|1;

if(l<=a[o].L && r>=a[o].R)
{
    a[o].setv = val;
    a[o].addv = 0;
    a[o].maxv = a[o].setv;
    a[o].minv = a[o].setv;
    a[o].sumv = a[o].setv*(a[o].R-a[o].L+1);
}
else
{
    pushdown(o);
    int M = a[o].L+(a[o].R-a[o].L)/2;

    if(l<=M)UpdateSet(l,r,val,lc);
    if(r>M)UpdateSet(l,r,val,rc);
    maintain(o);
}

}

void Query(int k,int l,int r,int o,int add)
{
if(a[o].setv >= 0) {
int v = a[o].setv + add + a[o].addv;
_sum[k] += v * (min(a[o].R,r)-max(a[o].L,l)+1);
_min[k] = min(_min[k], v);
_max[k] = max(_max[k], v);
} else if(l<=a[o].L && r>=a[o].R)
{
_sum[k]+=a[o].sumv+add*(a[o].R-a[o].L+1);
_min[k]=min(_min[k],a[o].minv+add);
_max[k] = max(_max[k],a[o].maxv+add);
}
else
{
pushdown(o);
int M = a[o].L+(a[o].R-a[o].L)/2;
if(l<=M)Query(k,l,r,o<
if(r>M)Query(k,l,r,o<<1|1,add+a[o].addv);
}
}

int main()
{
freopen("a.txt","r",stdin);
while(scanf("%d %d %d",&r,&c,&m)==3)
{
build(1,r*c,1); //一维问题
int type, x1,y1,x2,y2,val;

while(m--)
{
scanf("%d",&type);
switch(type)
{
case 1:
{
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&val);
for(int i=x1;i<=x2;i++)
{
UpdateAdd((i-1)*c+y1,(i-1)*c+y2,val,1);
}
}
break;
case 2:
{
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&val);
for(int i=x1;i<=x2;i++)
{
UpdateSet((i-1)*c+y1,(i-1)*c+y2,val,1);
}
}
break;
case 3:
{

                    memset(_sum,0,sizeof(_sum));
                    for(int i=0;i<=r;i++)
                    {
                        _max[i]=-inf;
                        _min[i]=inf;
                    }
                    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                    int anssum = 0, ansmax = -inf, ansmin = inf;

                    for(int i=x1;i<=x2;i++)
                    {
                        Query(i,(i-1)*c+y1,(i-1)*c+y2,1,0);
                        anssum+=_sum[i];
                        ansmin = min(ansmin,_min[i]);
                        ansmax = max(ansmax,_max[i]);
                    }
                    cout << anssum << " " << ansmin << " " << ansmax << endl;
                }
                break;
        }
    }
}
return 0;

}