题目链接 https://cn.vjudge.net/problem/UVA-11992
【题意】 有一个r行c列的全0矩阵，支持以下3种操作 1 x1 y1 x2 y2 v 子矩阵(x1,y1,x2,y2)的所有元素增加v（v>0） 2 x1 y1 x2 y2 v 子矩阵(x1,y1,x2,y2)的所有元素设为v（v>0） 3 x1 y1 x2 y2 查询子矩阵(x1,y1,x2,y2)的元素和，最小值，最大值 子矩阵(x1,y1,x2,y2)指的是满足x1<=x<=x2,y1<=y<=y2的所有元素(x,y)，输入保证任意时刻矩阵所有元素之和不超过1e9
【输入格式】 多组输入，每组第一行为3个整数r,c,m (m<=20000) 代表行数和列数以及操作次数，矩阵不超过20行，元素总数不超过1e6
【输出格式】 对于每个类型3操作，输出该子矩阵的元素和，最大值和最小值，用空格隔开
【思路】 因为总的元素个数不超过1e6且矩阵最多只有20行，所以可以把矩阵按行展开成一个一维的数组，然后对这个一维数组构造线段树。线段树要维护3个信息,区间和sum，最大值maxv和最小值minv，同时还要有两个区间更新标记，一个是操作1的增加标记addv，另一个是操作2的置数标记setv.线段树中有两种区间更新的操作，一个是Add对应操作1，另一个是Set对应操作2。 有两点需要注意的地方，一是在执行Set操作的时候，当前区间如果需要被置数，那么不仅该节点的setv被修改，同时还要将addv清零。二是在标记下传的时候，先处理setv操作，再处理addv操作。画一个线段树模拟一下操作过程就明白了。
#include<bits/stdc++.h> using namespace std; #define node tree[id] #define lson tree[id<<1] #define rson tree[id<<1|1] const int inf=2e9; const int maxn=1e6+50; struct Tree{ int left,right; int addv,setv; int sum,maxv,minv; }; int r,c,m; Tree tree[maxn<<2]; void pushup(int id){ node.sum=lson.sum+rson.sum; node.maxv=max(lson.maxv,rson.maxv); node.minv=min(lson.minv,rson.minv); } void pushdown(int id){ if(node.setv!=0 && node.left!=node.right){ lson.addv=rson.addv=0; lson.setv=lson.maxv=lson.minv=node.setv; lson.sum=lson.setv*(lson.right-lson.left+1); rson.setv=rson.maxv=rson.minv=node.setv; rson.sum=rson.setv*(rson.right-rson.left+1); node.setv=0; } if(node.addv!=0 && node.left!=node.right){ lson.addv+=node.addv; lson.maxv+=node.addv; lson.minv+=node.addv; lson.sum+=node.addv*(lson.right-lson.left+1); rson.addv+=node.addv; rson.maxv+=node.addv; rson.minv+=node.addv; rson.sum+=node.addv*(rson.right-rson.left+1); node.addv=0; } } void build(int id,int le,int ri){ node.left=le; node.right=ri; node.addv=node.setv=0; node.maxv=node.minv=node.sum=0; if(le==ri) return; int mid=(le+ri)>>1; build(id<<1,le,mid); build(id<<1|1,mid+1,ri); } Tree query(int id,int x,int y){ if(node.left==x && node.right==y){ return node; } pushdown(id); int mid=(node.left+node.right)>>1; if(x>mid) return query(id<<1|1,x,y); else if(y<=mid) return query(id<<1,x,y); else{ Tree a=query(id<<1,x,mid); Tree b=query(id<<1|1,mid+1,y); Tree ans; ans.sum=a.sum+b.sum; ans.maxv=max(a.maxv,b.maxv); ans.minv=min(a.minv,b.minv); return ans; } } void Add(int id,int x,int y,int v){ if(node.left==x && node.right==y){ node.addv+=v; node.sum+=v*(node.right-node.left+1); node.maxv+=v; node.minv+=v; return; } pushdown(id); int mid=(node.left+node.right)>>1; if(x>mid) Add(id<<1|1,x,y,v); else if(y<=mid) Add(id<<1,x,y,v); else{ Add(id<<1,x,mid,v); Add(id<<1|1,mid+1,y,v); } pushup(id); } void Set(int id,int x,int y,int v){ if(node.left==x && node.right==y){ node.addv=0; node.setv=v; node.sum=v*(node.right-node.left+1); node.maxv=node.minv=v; return; } pushdown(id); int mid=(node.left+node.right)>>1; if(x>mid) Set(id<<1|1,x,y,v); else if(y<=mid) Set(id<<1,x,y,v); else{ Set(id<<1,x,mid,v); Set(id<<1|1,mid+1,y,v); } pushup(id); } int main(){ while(scanf("%d%d%d",&r,&c,&m)==3){ build(1,1,r*c); while(m--){ int t,x1,y1,x2,y2,v; scanf("%d",&t); if(t==1){ scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v); for(int i=x1;i<=x2;++i) Add(1,(i-1)*c+y1,(i-1)*c+y2,v); } else if(t==2){ scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v); for(int i=x1;i<=x2;++i) Set(1,(i-1)*c+y1,(i-1)*c+y2,v); } else if(t==3){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); int minv=inf,maxv=-inf,sum=0; for(int i=x1;i<=x2;++i){ Tree ans=query(1,(i-1)*c+y1,(i-1)*c+y2); minv=min(minv,ans.minv); maxv=max(maxv,ans.maxv); sum+=ans.sum; } printf("%d %d %d\n",sum,minv,maxv); } } } return 0; }