题意：r*c的矩阵上，初始全部为0，有3中操作，子矩阵全部增加v,子矩阵值修改为v,查询子矩阵的最大值，最小值，和
分析：因为有setv和addv两种操作，那么需要开两个数组记录这个值，每次需要用到一个节点的儿子，那么就把该节点的setv,addv信息推过去，并且setv的优先级要高于addv，不过这样的后果就是，慢
不过这样写思维难度和编程难度降低了，一般并不会发生线段树不够快的情况
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=1e6+5; 7 const int INF=2e9; 8 typedef long long ll; 9 ll maxv[maxn<<2],minv[maxn<<2],sumv[maxn<<2],setv[maxn<<2],addv[maxn<<2]; 10 ll _sum,_min,_max,v; 11 int ql,qr,op; 12 13 void pushdown(int rt,int l,int r){ 14 int lc=rt*2,rc=rt*2+1; 15 if(setv[rt]!=0){ 16 setv[lc]=setv[rc]=setv[rt]; 17 minv[lc]=minv[rc]=setv[rt]; 18 maxv[lc]=maxv[rc]=setv[rt]; 19 setv[rt]=addv[lc]=addv[rc]=0; 20 int mid=l+(r-l)/2; 21 sumv[lc]=setv[lc]*(mid-l+1); 22 sumv[rc]=setv[rc]*(r-mid); 23 } 24 if(addv[rt]!=0){ 25 sumv[rt]=sumv[lc]+sumv[rc]+(r-l+1)*addv[rt]; 26 maxv[lc]+=addv[rt];maxv[rc]+=addv[rt]; 27 minv[lc]+=addv[rt];minv[rc]+=addv[rt]; 28 int mid=l+(r-l)/2; 29 sumv[lc]+=addv[rt]*(mid-l+1);sumv[rc]+=addv[rt]*(r-mid); 30 addv[lc]+=addv[rt];addv[rc]+=addv[rt]; 31 addv[rt]=0; 32 } 33 } 34 35 void update(int rt,int l,int r){ 36 if(ql<=l&&qr>=r){ 37 if(op==1){ 38 minv[rt]+=v;maxv[rt]+=v; 39 sumv[rt]+=v*(r-l+1); 40 addv[rt]+=v; 41 } 42 else{ 43 addv[rt]=0; 44 maxv[rt]=minv[rt]=setv[rt]=v; 45 sumv[rt]=v*(r-l+1); 46 } 47 return ; 48 } 49 int mid=l+(r-l)/2; 50 pushdown(rt,l,r); 51 if(ql<=mid)update(rt*2,l,mid); 52 if(qr>mid)update(rt*2+1,mid+1,r); 53 int lc=rt*2,rc=rt*2+1; 54 sumv[rt]=sumv[lc]+sumv[rc]; 55 minv[rt]=min(minv[lc],minv[rc]); 56 maxv[rt]=max(maxv[lc],maxv[rc]); 57 } 58 59 void query(int rt,int l,int r){ 60 if(ql<=l&&qr>=r){ 61 _sum+=sumv[rt]; 62 _min=min(_min,minv[rt]); 63 _max=max(_max,maxv[rt]); 64 return ; 65 } 66 pushdown(rt,l,r); 67 int mid=l+(r-l)/2; 68 if(ql<=mid)query(rt*2,l,mid); 69 if(qr>mid)query(rt*2+1,mid+1,r); 70 } 71 72 void init(){ 73 memset(minv,0,sizeof(minv)); 74 memset(maxv,0,sizeof(maxv)); 75 memset(sumv,0,sizeof(sumv)); 76 memset(setv,0,sizeof(setv)); 77 memset(addv,0,sizeof(addv)); 78 } 79 80 int main(){ 81 int r,c,n,m,t,x1,x2,y1,y2; 82 while(~scanf("%d%d%d",&r,&c,&m)){ 83 init(); 84 n=r*c; 85 while(m--){ 86 scanf("%d%d%d%d%d",&t,&x1,&y1,&x2,&y2); 87 if(t==1){ 88 op=1;scanf("%lld",&v); 89 for(int i=x1;i<=x2;i++){ 90 ql=(i-1)*c+y1; 91 qr=(i-1)*c+y2; 92 update(1,1,n); 93 } 94 } 95 else if(t==2){ 96 scanf("%lld",&v);op=2; 97 for(int i=x1;i<=x2;i++){ 98 ql=(i-1)*c+y1; 99 qr=(i-1)*c+y2; 100 update(1,1,n); 101 } 102 } 103 else{ 104 _sum=0;_max=-INF;_min=INF; 105 for(int i=x1;i<=x2;i++){ 106 ql=(i-1)*c+y1; 107 qr=(i-1)*c+y2; 108 query(1,1,n); 109 } 110 cout<<_sum<<" "<<_min<<" "<<_max<<endl; 111 } 112 } 113 } 114 return 0; 115 }