链接:Miku
------------------
没有UVa账号唉
-------------------
卡了蒟蒻一天，因为漏掉了懒标记的下放。
线段树的巨大码量，为bug提供了绝佳的掩护
写完后，我哭了
人间的喜悦就这么简单吧
---------------------
对于一个矩阵，有两个操作，子矩阵加v或者子矩阵变为v
询问子矩阵最大值，最小值和和
-------------------------
最简单的想法是线段树，不过太难实现了（对于本蒟蒻），所以说还是可以用一维线段树做的
这矩阵虽然很长，但是不宽，我们完全可以把每一行首位相接，然后拼成一维的
--------------------------
修改 两个操作，区间赋值比区间加有限度要高，而且区间赋值了之后就没必要加了，所以说
直接把加变为零就可以了
----------------------------
查询 三个分别查就可以了
--------------------------------
#include<iostream> #include<cstdio> using namespace std; int n,m; const int maxnn=1e7+9; long long sum[maxnn],lazyadd[maxnn],lazychange[maxnn]; int x,y,f; int q,xx,yy; long long maxn[maxnn],minn[maxnn]; long long k; int s; long long ans,ans1,ans2; void pushdown(int x,int l,int r){ if(lazychange[x]!=0){//很显然的修改 int mid=(l+r)>>1; lazyadd[x<<1]=0; lazyadd[x<<1|1]=0; lazychange[x<<1|1]=lazychange[x<<1]=lazychange[x]; sum[x<<1]=(mid-l+1)*lazychange[x]; sum[x<<1|1]=(r-mid)*lazychange[x]; maxn[x<<1]=lazychange[x]; maxn[x<<1|1]=lazychange[x]; minn[x<<1]=lazychange[x]; minn[x<<1|1]=lazychange[x]; lazychange[x]=0; } if (lazyadd[x] != 0){ int mid=(l+r)>>1; lazyadd[x<<1]+=lazyadd[x]; sum[x<<1]+=lazyadd[x]*(mid-l+1); lazyadd[x<<1|1]+=lazyadd[x]; sum[x<<1|1]+=lazyadd[x]*(r-mid); maxn[x<<1]+=lazyadd[x]; maxn[x<<1|1]+=lazyadd[x]; minn[x<<1]+=lazyadd[x]; minn[x<<1|1]+=lazyadd[x]; lazyadd[x]=0; } return ; } void pushup(int x){ sum[x]=sum[x<<1]+sum[x<<1|1]; maxn[x]=max(maxn[x<<1],maxn[x<<1|1]); minn[x]=min(minn[x<<1],minn[x<<1|1]); return ; } void update1(int x,int l,int r,int L,int R,long long d){ if(L<=l&&r<=R){ lazyadd[x]+=d; sum[x]+=d*(r-l+1); maxn[x]+=d; minn[x]+=d; return ; } int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) update1(x<<1,l,mid,L,R,d); if(R>mid) update1(x<<1|1,mid+1,r,L,R,d); pushup(x); } void update3(int x,int l,int r,int L,int R,long long d){ if(L<=l&&r<=R){ lazyadd[x]=0;//记得赋值为0 lazychange[x]=d; maxn[x]=d; minn[x]=d; sum[x]=d*(r-l+1); return ; } int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) update3(x<<1,l,mid,L,R,d); if(R>mid) update3(x<<1|1,mid+1,r,L,R,d); pushup(x); } long long query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return sum[x]; } long long ans=0; int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) ans+=query(x<<1,l,mid,L,R); if(R>mid) ans+=query(x<<1|1,mid+1,r,L,R); return ans; } long long query2(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return maxn[x]; } long long ans=0; int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) ans=max(query2(x<<1,l,mid,L,R),ans); if(R>mid) ans=max(ans,query2(x<<1|1,mid+1,r,L,R)); return ans; } long long query3(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return minn[x]; } long long ans=0x7f7f7f7f; int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) ans=min(ans,query3(x<<1,l,mid,L,R)); if(R>mid) ans=min(ans,query3(x<<1|1,mid+1,r,L,R)); return ans; } int main(){ scanf("%d%d%d",&n,&m,&q); s=n*m; for(int i=1;i<=q;++i){ scanf("%d",&f); if(f==1){ scanf("%d%d%d%d%lld",&x,&y,&xx,&yy,&k);//一操作 for(int j=x-1;j<xx;++j){ update1(1,1,s,y+j*m,yy+j*m,k); } } if(f==2){ scanf("%d%d%d%d%lld",&x,&y,&xx,&yy,&k);//二操作 for(int j=x-1;j<xx;++j){ update3(1,1,s,y+j*m,yy+j*m,k); } } if(f==3){ scanf("%d%d%d%d",&x,&y,&xx,&yy);//查询时间 ans=0; for(int j=x-1;j<xx;++j){ ans+=query(1,1,s,y+j*m,yy+j*m); } printf("%lld ",ans); ans=0x7f7f7f;//先是最小值 for(int j=x-1;j<xx;++j){ ans=min(ans,query3(1,1,s,y+j*m,yy+j*m)); } printf("%lld ",ans); ans=0; for(int j=x-1;j<xx;++j){ ans=max(ans,query2(1,1,s,y+j*m,yy+j*m)); } printf("%lld ",ans); } } return 0; }