input
r c m r<=20,1<=m<=20000
m行操作
1 x1 y1 x2 y2 v add v
2 x1 y1 x2 y2 v set v
3 x1 y1 x2 y2 查询该矩阵中的sum,max,min
output
对于每个3操作输出sum,max,min
做法：每行建一颗线段树
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#define INF 0x7fffffff
#define MAX 1000000 using namespace std; struct node
{
int v,addv,setv,sum,min,max;
};
int r,c,m,x1,yy1,x2,yy2,v,op,suma,mina,maxa;
node a[][MAX*];
void pushdown(int &l,int &r,int &k,int&i)
{
if(a[i][k].setv==&&a[i][k].addv==) return;
int m=l+((r-l)>>),lc=k<<,rc=k<<|,allv=a[i][k].setv+a[i][k].addv;
if(a[i][k].setv) //有set操作时优先将set操作pushdown
{
a[i][lc].addv=a[i][rc].addv=a[i][k].addv;
a[i][lc].v=a[i][rc].v=a[i][lc].setv=a[i][rc].setv=a[i][k].setv;
a[i][lc].min=a[i][rc].min=a[i][lc].max=a[i][rc].max=allv;
a[i][lc].sum=(m-l+)*allv;
a[i][rc].sum=(r-m)*allv;
a[i][k].setv=a[i][k].addv=;
}
else //无set操作时只是add操作也要pushdown
{
a[i][lc].addv+=a[i][k].addv;
a[i][rc].addv+=a[i][k].addv;
a[i][lc].min+=a[i][k].addv;
a[i][rc].min+=a[i][k].addv;
a[i][lc].max+=a[i][k].addv;
a[i][rc].max+=a[i][k].addv;
a[i][lc].sum+=(m-l+)*a[i][k].addv;
a[i][rc].sum+=(r-m)*a[i][k].addv;
a[i][k].addv=;
}
// printf("l:%d r:%d setv:%d add:%d\n",l,r,a[i][k].setv,a[i][k].addv);
}
void reset(int &l,int &r,int &k,int&i)
{
int m=l+((r-l)>>),lc=k<<,rc=k<<|;
a[i][k].sum=a[i][lc].sum+a[i][rc].sum+(r-l+)*a[i][k].addv;
a[i][k].min=min(a[i][lc].min,a[i][rc].min)+a[i][k].addv;
a[i][k].max=max(a[i][lc].max,a[i][rc].max)+a[i][k].addv;
}
void setupdate(int l,int r,int k,int &i)
{
int lc=k<<,rc=k<<|;
if(yy1<=l&&yy2>=r)
{
a[i][k].min=a[i][k].max=a[i][k].setv=a[i][k].v=v;
a[i][k].addv=;
a[i][k].sum=(r-l+)*v;
//printf("l:%d r:%d setv:%d add:%d\n",l,r,a[i][k].setv,a[i][k].addv);
return;
}
pushdown(l,r,k,i);
int m=l+((r-l)>>);
if(yy1<=m) setupdate(l,m,lc,i);
if(yy2>m) setupdate(m+,r,rc,i);
reset(l,r,k,i);
}
void addupdate(int l,int r,int k,int &i)
{
int lc=k<<,rc=k<<|;
if(yy1<=l&&yy2>=r)
{
a[i][k].addv+=v;
a[i][k].sum+=(r-l+)*v;
a[i][k].min+=v;
a[i][k].max+=v;
return;
}
pushdown(l,r,k,i);
int m=l+((r-l)>>);
if(yy1<=m) addupdate(l,m,lc,i);
if(yy2>m) addupdate(m+,r,rc,i);
reset(l,r,k,i);
}
void query(int l,int r,int k,int& i,int add)
{
if(a[i][k].setv)
{
int allv=add+a[i][k].v+a[i][k].addv;
suma+=allv*(min(r,yy2)-max(l,yy1)+);
mina=min(mina,allv);
maxa=max(maxa,allv);
//printf("addv:%d all:%d %d %d\n",a[i][k].addv,add,mina,maxa);
return;
}
if(yy1<=l&&yy2>=r)
{
suma+=a[i][k].sum+(r-l+)*add;
mina=min(mina,a[i][k].min+add);
maxa=max(maxa,a[i][k].max+add);
return;
}
int m=l+((r-l)>>);
if(yy1<=m) query(l,m,k<<,i,add+a[i][k].addv);
if(yy2>m) query(m+,r,k<<|,i,add+a[i][k].addv);
}
int main()
{
freopen("/home/user/桌面/in","r",stdin);
while(scanf("%d%d%d",&r,&c,&m)==)
{
for(int i=;i<=r;i++) memset(a[i],,sizeof(a[][])**c);
//memset(a,0,sizeof(a));
while(m--)
{
scanf("%d%d%d%d%d",&op,&x1,&yy1,&x2,&yy2);
if(op==)
{
scanf("%d",&v);
for(int i=x1;i<=x2;i++) setupdate(,c,,i);
//for(int i=1;i<3*c;i++) printf("%d:%d %d\n",i,a[3][i].setv,a[3][i].addv);
//puts("set");
}
else if(op==)
{
scanf("%d",&v);
for(int i=x1;i<=x2;i++) addupdate(,c,,i);
//for(int i=1;i<3*c;i++) printf("%d:%d %d\n",i,a[3][i].setv,a[3][i].addv);
//puts("add");
}
else
{
suma=;
mina=INF;
maxa=-INF-;
//printf("row:%d-%d\ncol:%d-%d\n",x1,x2,yy1,yy2);
//for(int i=1;i<=r;i++) printf("rowsum:%d\n",a[i][1].sum);
for(int i=x1;i<=x2;i++) query(,c,,i,);
printf("%d %d %d\n",suma,mina,maxa);
}
}
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}