刘汝佳书上的题目，可以把矩形的每一行都开一棵线段树，最多也就20棵，空间也炸不了。然后就是线段树操作了。
注意：下传的时候最大，最小值也要更新。同样注意标记的优先级顺序。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=4e5+7; 4 const int N=550; 5 struct node{ 6 int l,r,sum,lazy1,lazy2,mi,mx; 7 }tree[22][maxn*4]; 8 int n,m,t; 9 int opt,xx,yy,xxx,yyy,v; 10 int ans1,ans2,ans3; 11 void pushdown(int id,int now){ 12 if(tree[id][now].lazy1!=-1){ 13 tree[id][now<<1].sum=(tree[id][now<<1].r-tree[id][now<<1].l+1)*tree[id][now].lazy1; 14 tree[id][now<<1|1].sum=(tree[id][now<<1|1].r-tree[id][now<<1|1].l+1)*tree[id][now].lazy1; 15 tree[id][now<<1].mi=tree[id][now].lazy1; 16 tree[id][now<<1].mx=tree[id][now].lazy1; 17 tree[id][now<<1|1].mi=tree[id][now].lazy1; 18 tree[id][now<<1|1].mx=tree[id][now].lazy1; 19 tree[id][now<<1].lazy1=tree[id][now].lazy1; 20 tree[id][now<<1|1].lazy1=tree[id][now].lazy1; 21 tree[id][now<<1].lazy2=tree[id][now<<1|1].lazy2=0; 22 tree[id][now].lazy1=-1; 23 } 24 if(tree[id][now].lazy2){ 25 tree[id][now<<1].sum+=(tree[id][now<<1].r-tree[id][now<<1].l+1)*tree[id][now].lazy2; 26 tree[id][now<<1|1].sum+=(tree[id][now<<1|1].r-tree[id][now<<1|1].l+1)*tree[id][now].lazy2; 27 tree[id][now<<1].mi+=tree[id][now].lazy2; 28 tree[id][now<<1].mx+=tree[id][now].lazy2; 29 tree[id][now<<1|1].mi+=tree[id][now].lazy2; 30 tree[id][now<<1|1].mx+=tree[id][now].lazy2; 31 tree[id][now<<1].lazy2+=tree[id][now].lazy2; 32 tree[id][now<<1|1].lazy2+=tree[id][now].lazy2; 33 tree[id][now].lazy2=0; 34 } 35 } 36 void pushup(int id,int now){ 37 tree[id][now].sum=tree[id][now<<1].sum+tree[id][now<<1|1].sum; 38 tree[id][now].mi=min(tree[id][now<<1].mi,tree[id][now<<1|1].mi); 39 tree[id][now].mx=max(tree[id][now<<1].mx,tree[id][now<<1|1].mx); 40 } 41 void build(int id,int now,int l,int r){ 42 tree[id][now].l=l,tree[id][now].r=r,tree[id][now].lazy1=-1; 43 if(l==r) return; 44 int mid=(l+r)>>1; 45 build(id,now<<1,l,mid); 46 build(id,now<<1|1,mid+1,r); 47 pushup(id,now); 48 } 49 void update1(int id,int now,int l,int r,int v){ 50 if(tree[id][now].l>=l&&tree[id][now].r<=r){ 51 tree[id][now].sum=(tree[id][now].r-tree[id][now].l+1)*v; 52 tree[id][now].mi=v; 53 tree[id][now].mx=v; 54 tree[id][now].lazy1=v; 55 tree[id][now].lazy2=0; 56 return; 57 } 58 pushdown(id,now); 59 int mid=(tree[id][now].l+tree[id][now].r)>>1; 60 if(l<=mid) update1(id,now<<1,l,r,v); 61 if(r>mid) update1(id,now<<1|1,l,r,v); 62 pushup(id,now); 63 } 64 void update2(int id,int now,int l,int r,int v){ 65 if(tree[id][now].l>=l&&tree[id][now].r<=r){ 66 tree[id][now].sum+=(tree[id][now].r-tree[id][now].l+1)*v; 67 tree[id][now].mi+=v; 68 tree[id][now].mx+=v; 69 tree[id][now].lazy2+=v; 70 return; 71 } 72 pushdown(id,now); 73 int mid=(tree[id][now].l+tree[id][now].r)>>1; 74 if(l<=mid) update2(id,now<<1,l,r,v); 75 if(r>mid) update2(id,now<<1|1,l,r,v); 76 pushup(id,now); 77 } 78 int querymax(int id,int now,int l,int r){ 79 if(tree[id][now].l>=l&&tree[id][now].r<=r) return tree[id][now].mx; 80 pushdown(id,now); 81 int mid=(tree[id][now].l+tree[id][now].r)>>1; 82 int val=-0x3f3f3f3f; 83 if(l<=mid) val=max(val,querymax(id,now<<1,l,r)); 84 if(r>mid) val=max(val,querymax(id,now<<1|1,l,r)); 85 return val; 86 } 87 int querymin(int id,int now,int l,int r){ 88 if(tree[id][now].l>=l&&tree[id][now].r<=r) return tree[id][now].mi; 89 pushdown(id,now); 90 int mid=(tree[id][now].l+tree[id][now].r)>>1; 91 int val=0x3f3f3f3f; 92 if(l<=mid) val=min(val,querymin(id,now<<1,l,r)); 93 if(r>mid) val=min(val,querymin(id,now<<1|1,l,r)); 94 return val; 95 } 96 int querysum(int id,int now,int l,int r){ 97 if(tree[id][now].l>=l&&tree[id][now].r<=r) return tree[id][now].sum; 98 pushdown(id,now); 99 int mid=(tree[id][now].l+tree[id][now].r)>>1; 100 int val=0; 101 if(l<=mid) val+=querysum(id,now<<1,l,r); 102 if(r>mid) val+=querysum(id,now<<1|1,l,r); 103 return val; 104 } 105 int main(){ 106 while(scanf("%d%d%d",&n,&m,&t)!=EOF){ 107 memset(tree,0,sizeof(tree)); 108 for(int i=1;i<=n;i++) build(i,1,1,m); 109 for(int i=1;i<=t;i++){ 110 scanf("%d",&opt); 111 if(opt==1){ 112 scanf("%d%d%d%d%d",&xx,&yy,&xxx,&yyy,&v); 113 for(int i=xx;i<=xxx;i++) update2(i,1,yy,yyy,v); 114 } 115 if(opt==2){ 116 scanf("%d%d%d%d%d",&xx,&yy,&xxx,&yyy,&v); 117 for(int i=xx;i<=xxx;i++) update1(i,1,yy,yyy,v); 118 } 119 if(opt==3){ 120 ans1=0,ans2=0x3f3f3f3f,ans3=-0x3f3f3f3f; 121 scanf("%d%d%d%d",&xx,&yy,&xxx,&yyy); 122 for(int i=xx;i<=xxx;i++) ans1+=querysum(i,1,yy,yyy); 123 for(int i=xx;i<=xxx;i++) ans2=min(ans2,querymin(i,1,yy,yyy)); 124 for(int i=xx;i<=xxx;i++) ans3=max(ans3,querymax(i,1,yy,yyy)); 125 printf("%d %d %d ",ans1,ans2,ans3); 126 } 127 } 128 } 129 return 0; 130 }