UVA11992：FastMatrixOperations

#include
#include
#include
#include
#define MAXN 1000005
using namespace std;
struct Node{
int sumv,maxv,minv,tag_add,tag_change;
Node(int p1=0,int p2=0,int p3=0,int p4=0,int p5=0){
sumv=p1,maxv=p3,minv=p2,tag_add=p4,tag_change=p5;
}
}dat[22][MAXN<<2];
int a[22][MAXN];
Node Merge(Node t1,Node t2){
if(t1.tag_add==-1)return t2;
if(t2.tag_add==-1)return t1;
Node ret;
ret.sumv=t1.sumv+t2.sumv;
ret.maxv=max(t1.maxv,t2.maxv);
ret.minv=min(t1.minv,t2.minv);
return ret;
}
void build(Node d[],int x,int k,int L,int R){
if(L+1==R){
d[k].sumv=d[k].maxv=d[k].minv=a[x][L];
return;
}
build(d,x,k<<1,L,(L+R)>>1);
build(d,x,k<<1|1,(L+R)>>1,R);
d[k]=Merge(d[k<<1],d[k<<1|1]);
}
void pushdown(Node d[],int k,int L,int R){
int lc=(k<<1),rc=(k<<1|1);
if(d[k].tag_change){
d[lc].tag_add=0;
d[lc].tag_change=d[k].tag_change;
d[lc].sumv=d[k].tag_change*(((L+R)>>1)-L);
d[lc].maxv=d[k].tag_change;
d[lc].minv=d[k].tag_change;
d[rc].tag_add=0;
d[rc].tag_change=d[k].tag_change;
d[rc].sumv=d[k].tag_change*(R-((L+R)>>1));
d[rc].maxv=d[k].tag_change;
d[rc].minv=d[k].tag_change;
d[k].tag_change=0;
}
if(d[k].tag_add){
d[lc].tag_add+=d[k].tag_add;
d[lc].sumv+=d[k].tag_add*(((L+R)>>1)-L);
d[lc].maxv+=d[k].tag_add;
d[lc].minv+=d[k].tag_add;
d[rc].tag_add+=d[k].tag_add;
d[rc].sumv+=d[k].tag_add*(R-((L+R)>>1));
d[rc].maxv+=d[k].tag_add;
d[rc].minv+=d[k].tag_add;
d[k].tag_add=0;
}
}
void add(Node d[],int a,int b,int k,int L,int R,int x){
if(b<=L||R<=a){
return;
}
else if(a<=L&&R<=b){
d[k].tag_add+=x;
d[k].sumv+=x*(R-L);
d[k].maxv+=x;
d[k].minv+=x;
}
else{
if(d[k].tag_add||d[k].tag_change){
pushdown(d,k,L,R);
}
add(d,a,b,k<<1,L,(L+R)>>1,x);
add(d,a,b,k<<1|1,(L+R)>>1,R,x);
d[k]=Merge(d[k<<1],d[k<<1|1]);
}
}
void change(Node d[],int a,int b,int k,int L,int R,int x){
if(b<=L||R<=a){
return;
}
else if(a<=L&&R<=b){
d[k].tag_add=0;
d[k].tag_change=x;
d[k].sumv=x*(R-L);
d[k].maxv=x;
d[k].minv=x;
}
else{
if(d[k].tag_add||d[k].tag_change){
pushdown(d,k,L,R);
}
change(d,a,b,k<<1,L,(L+R)>>1,x);
change(d,a,b,k<<1|1,(L+R)>>1,R,x);
d[k]=Merge(d[k<<1],d[k<<1|1]);
}
}
Node query(Node d[],int a,int b,int k,int L,int R){
if(b<=L||R<=a){
return Node(-1,-1,-1,-1,-1);
}
else if(a<=L&&R<=b){
return d[k];
}
else{
if(d[k].tag_add||d[k].tag_change){
pushdown(d,k,L,R);
}
Node lc=query(d,a,b,k<<1,L,(L+R)>>1);
Node rc=query(d,a,b,k<<1|1,(L+R)>>1,R);
return Merge(lc,rc);
}
}
void debug(Node d[],int k,int L,int R){
if(d[k].tag_add||d[k].tag_change){
pushdown(d,k,L,R);
}
if(L+1==R){
printf("%d ",d[k]);
return;
}
debug(d,k<<1,L,(L+R)>>1);
debug(d,k<<1|1,(L+R)>>1,R);
}
int m,n,T;
void solve(){
for(int i=1;i<=m;i++){
build(dat[i],i,1,1,n+1);
}
while(T--){
int p;scanf("%d",&p);
int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(1==p){
int v;scanf("%d",&v);
for(int i=x1;i<=x2;i++){
add(dat[i],y1,y2+1,1,1,n+1,v);
}
}
else if(2==p){
int v;scanf("%d",&v);
for(int i=x1;i<=x2;i++){
change(dat[i],y1,y2+1,1,1,n+1,v);
}
}
else{
Node ans=query(dat[x1],y1,y2+1,1,1,n+1);
for(int i=x1+1;i<=x2;i++){
Node t=query(dat[i],y1,y2+1,1,1,n+1);
ans.sumv+=t.sumv;
ans.maxv=max(ans.maxv,t.maxv);
ans.minv=min(ans.minv,t.minv);
}
printf("%d %d %d\n",ans.sumv,ans.minv,ans.maxv);
}
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.in","w",stdout);
while(~scanf("%d%d%d",&m,&n,&T)){
solve();
}
}