题意：矩阵加，矩阵覆盖，矩阵和查询
题目中说了不超过20行，所以不用二维线段树，20颗线段树即可搞定
#include#include #include #define N 1000001using namespace std;int n,m,q,xx1,xx2,yy1,yy2,type;int opl,opr,w,tot;long long key[N<<2],tag_add[N<<2],tag_set[N<<2],tmin[N<<2],tmax[N<<2],sum,minn,maxn;int root[21],lc[N<<2],rc[N<<2];void clear(){ tot=0; memset(root,0,sizeof(root)); memset(lc,0,sizeof(lc)); memset(rc,0,sizeof(rc)); memset(key,0,sizeof(key)); memset(tmin,0,sizeof(tmin)); memset(tmax,0,sizeof(tmax)); memset(tag_add,0,sizeof(tag_add)); memset(tag_set,0,sizeof(tag_set));}void down_add(int k,int l,int r){ if(!lc[k]) lc[k]=++tot; if(!rc[k]) rc[k]=++tot; int mid=l+r>>1; if(tag_set[lc[k]]) tag_set[lc[k]]+=tag_add[k]; else tag_add[lc[k]]+=tag_add[k]; key[lc[k]]+=(mid-l+1)*tag_add[k]; tmin[lc[k]]+=tag_add[k]; tmax[lc[k]]+=tag_add[k]; if(tag_set[rc[k]]) tag_set[rc[k]]+=tag_add[k]; else tag_add[rc[k]]+=tag_add[k]; key[rc[k]]+=(r-mid)*tag_add[k]; tmin[rc[k]]+=tag_add[k]; tmax[rc[k]]+=tag_add[k]; tag_add[k]=0;}void down_set(int k,int l,int r){ if(!lc[k]) lc[k]=++tot; if(!rc[k]) rc[k]=++tot; int mid=l+r>>1; key[lc[k]]=(mid-l+1)*tag_set[k]; key[rc[k]]=(r-mid)*tag_set[k]; tmin[lc[k]]=tmax[lc[k]]=tmin[rc[k]]=tmax[rc[k]]=tag_set[k]; tag_add[lc[k]]=tag_add[rc[k]]=0; tag_set[lc[k]]=tag_set[rc[k]]=tag_set[k]; tag_set[k]=0;}void query(int k,int l,int r){ if(!k) return; if(l>=opl && r<=opr) { sum+=key[k]; minn=min(minn,tmin[k]); maxn=max(maxn,tmax[k]); return ; } if(tag_set[k]) down_set(k,l,r); if(tag_add[k]) down_add(k,l,r); int mid=l+r>>1; if(opl<=mid) query(lc[k],l,mid); if(opr>mid) query(rc[k],mid+1,r);}void add(int &k,int l,int r){ if(!k) k=++tot; if(l>=opl && r<=opr) { key[k]+=w*(r-l+1); tmin[k]+=w; tmax[k]+=w; tag_add[k]+=w; return; } if(tag_set[k]) down_set(k,l,r); if(tag_add[k]) down_add(k,l,r); int mid=l+r>>1; if(opl<=mid) add(lc[k],l,mid); if(opr>mid) add(rc[k],mid+1,r); key[k]=key[lc[k]]+key[rc[k]]; tmin[k]=min(tmin[lc[k]],tmin[rc[k]]); tmax[k]=max(tmax[lc[k]],tmax[rc[k]]);}void set(int &k,int l,int r){ if(!k) k=++tot; if(l>=opl && r<=opr) { key[k]=(r-l+1)*w; tag_add[k]=0; tag_set[k]=w; tmin[k]=tmax[k]=w; return; } if(tag_set[k]) down_set(k,l,r); if(tag_add[k]) down_add(k,l,r); int mid=l+r>>1; if(opl<=mid) set(lc[k],l,mid); if(opr>mid) set(rc[k],mid+1,r); key[k]=key[lc[k]]+key[rc[k]]; tmin[k]=min(tmin[lc[k]],tmin[rc[k]]); tmax[k]=max(tmax[lc[k]],tmax[rc[k]]);}int main(){ while(scanf("%d%d%d",&n,&m,&q)!=EOF) { for(int j=1;j<=q;j++) { scanf("%d%d%d%d%d",&type,&xx1,&yy1,&xx2,&yy2); if(type!=3) scanf("%d",&w); sum=0; minn=2e15; maxn=-2e15; opl=yy1; opr=yy2; for(int i=xx1;i<=xx2;i++) { if(type==1) add(root[i],1,m); else if(type==2) set(root[i],1,m); else query(root[i],1,m); } if(type==3) { if(minn==2e15) minn=0; if(maxn==-2e15) maxn=0; printf("%lld %lld %lld\n",sum,minn,maxn); } } clear(); }}