有一个 r 行 c 列的全 0 矩阵, 有以下三种操作.
1 X1 Y1 X2 Y2 v 子矩阵 (X1,Y1,X2,Y2) 的元素加 v
2 X1 Y1 X2 Y2 v 子矩阵 (X1,Y1,X2,Y2) 的元素变为 v
3 X1 Y1 X2 Y2 查询子矩阵 (X1,Y1,X2,Y2) 的和, 最大值, 最小值
子矩阵 (X1,Y1,X2,Y2) 满足 X1<=X<=X2 Y1<=Y<=Y2 的所有元素 (X1,Y2).
- #include
- #include
- #include
- #include
- using namespace std;
- const int maxn=1e7+9;
- int tree[30],r,c,m,T;
- int mi[maxn],ma[maxn],sum[maxn],lson[maxn],rson[maxn],tag[maxn],st[maxn];
- inline int max(int a,int b){return a>b?a:b;}
- inline int min(int a,int b){return a<b?a:b;}
- inline void pushup(int rt)
- {
- ma[rt]=max(ma[lson[rt]],ma[rson[rt]]);
- mi[rt]=min(mi[lson[rt]],mi[rson[rt]]);
- sum[rt]=sum[lson[rt]]+sum[rson[rt]];
- }
- inline void pushdown(int rt,int l,int r)
- {
- int mid=(l+r)>>1;
- if(st[rt])
- {
- st[lson[rt]]=st[rt];
- st[rson[rt]]=st[rt];
- mi[lson[rt]]=st[rt];
- ma[lson[rt]]=st[rt];
- mi[rson[rt]]=st[rt];
- ma[rson[rt]]=st[rt];
- sum[lson[rt]]=st[rt]*(mid-l+1);
- sum[rson[rt]]=st[rt]*(r-mid);
- tag[lson[rt]]=tag[rson[rt]]=0;
- st[rt]=0;
- }
- if(tag[rt])
- {
- tag[lson[rt]]+=tag[rt];
- tag[rson[rt]]+=tag[rt];
- mi[lson[rt]]+=tag[rt];
- ma[lson[rt]]+=tag[rt];
- mi[rson[rt]]+=tag[rt];
- ma[rson[rt]]+=tag[rt];
- sum[lson[rt]]+=tag[rt]*(mid-l+1);
- sum[rson[rt]]+=tag[rt]*(r-mid);
- tag[rt]=0;
- }
- }
- inline int build(int l,int r)
- {
- int rt=++T;
- tag[rt]=sum[rt]=mi[rt]=ma[rt]=st[rt]=0;
- if(l==r)
- {
- sum[rt]=mi[rt]=ma[rt]=0;
- lson[rt]=rson[rt]=0;
- return rt;
- }
- int mid=(l+r)>>1;
- lson[rt]=build(l,mid);
- rson[rt]=build(mid+1,r);
- pushup(rt);
- return rt;
- }
- inline void add(int rt,int l,int r,int ll,int rr,int w)
- {
- if(ll<=l&&rr>=r)
- {
- tag[rt]+=w;
- sum[rt]+=w*(r-l+1);
- mi[rt]+=w;
- ma[rt]+=w;
- return ;
- }
- pushdown(rt,l,r);
- int mid=(l+r)>>1;
- if(ll<=mid) add(lson[rt],l,mid,ll,rr,w);
- if(mid<rr) add(rson[rt],mid+1,r,ll,rr,w);
- pushup(rt);
- }
- inline void set(int rt,int l,int r,int ll,int rr,int w)
- {
- if(ll<=l&&rr>=r)
- {
- sum[rt]=(r-l+1)*w;
- tag[rt]=0;
- ma[rt]=w;
- mi[rt]=w;
- st[rt]=w;
- return ;
- }
- pushdown(rt,l,r);
- int mid=(l+r)>>1;
- if(ll<=mid) set(lson[rt],l,mid,ll,rr,w);
- if(mid<rr) set(rson[rt],mid+1,r,ll,rr,w);
- pushup(rt);
- }
- inline int all_query(int rt,int l,int r,int ll,int rr)
- {
- if(ll<=l&&rr>=r)
- return sum[rt];
- pushdown(rt,l,r);
- int mid=(l+r)>>1;
- int ans=0;
- if(ll<=mid) ans+=all_query(lson[rt],l,mid,ll,rr);
- if(rr>mid) ans+=all_query(rson[rt],mid+1,r,ll,rr);
- return ans;
- }
- inline int max_query(int rt,int l,int r,int ll,int rr)
- {
- if(ll<=l&&rr>=r)
- return ma[rt];
- pushdown(rt,l,r);
- int mid=(l+r)>>1;
- int ans=-0x3f3f3f3f;
- if(ll<=mid) ans=max(ans,max_query(lson[rt],l,mid,ll,rr));
- if(rr>mid) ans=max(ans,max_query(rson[rt],mid+1,r,ll,rr));
- return ans;
- }
- inline int min_query(int rt,int l,int r,int ll,int rr)
- {
- if(ll<=l&&rr>=r)
- return mi[rt];
- pushdown(rt,l,r);
- int mid=(l+r)>>1;
- int ans=0x3f3f3f3f;
- if(ll<=mid) ans=min(ans,min_query(lson[rt],l,mid,ll,rr));
- if(rr>mid) ans=min(ans,min_query(rson[rt],mid+1,r,ll,rr));
- return ans;
- }
- int main()
- {
- while(~scanf("%d%d%d",&r,&c,&m))
- {
- T=0;
- for(register int i=1;i<=r;i++)
- tree[i]=build(1,c);
- for(register int i=1;i<=m;i++)
- {
- int opt,x1,x2,y1,y2;
- scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
- if(opt==1)
- {
- int v;scanf("%d",&v);
- for(register int i=x1;i<=x2;i++)
- add(tree[i],1,c,y1,y2,v);
- }
- if(opt==2)
- {
- int v;scanf("%d",&v);
- for(register int i=x1;i<=x2;i++)
- set(tree[i],1,c,y1,y2,v);
- }
- if(opt==3)
- {
- int all=0,minn=0x3f3f3f,maxx=-0x3f3f3f;
- for(register int i=x1;i<=x2;i++)
- {
- all+=all_query(tree[i],1,c,y1,y2);
- minn=min(minn,min_query(tree[i],1,c,y1,y2));
- maxx=max(maxx,max_query(tree[i],1,c,y1,y2));
- }
- printf("%d %d %d\n",all,minn,maxx);
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2839913.html