特别是,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;
}