uva11992:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3143
題意：給你n*m的矩陣初始化的時候矩陣里面的元素全部是0，對于這個矩陣有3中操作。
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）子矩陣的和，以及最小值和最大值
題解：很明顯是二維線段樹維護，并且題目中的n不超過20.打20棵線段樹就可以解決。這里的置成v，可以看成是*0+v，加上v可以看成*1+v；
線段樹維護一個mul乘數，add加數，sum總和，minn最小值，maxn最大值。注意pushdown時候對子節點先*后加。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=100002; 7 struct SegTree{ 8 int l,r; 9 int add,mul; 10 int sum,minn,maxn; 11 void init(){ 12 add=0;mul=1; 13 } 14 inline int mid(){ 15 return (l+r)>> 1; 16 } 17 inline int len(){ 18 return r-l+1; 19 } 20 void to_mul(int m){//每次*一個數，那么之前add的數此時也要*這個數 21 sum *=m; 22 minn*=m; 23 maxn*=m; 24 mul *= m; 25 add *= m; 26 } 27 void to_add(int a){ 28 minn+=a; 29 maxn+=a; 30 sum +=a* len(); 31 add +=a; 32 } 33 }T[23][N*4]; 34 void pushdown(int num,int rt){//這里一定要注意 35 T[num][rt<<1].to_mul(T[num][rt].mul); 36 T[num][rt<<1|1].to_mul(T[num][rt].mul); 37 T[num][rt<<1].to_add(T[num][rt].add); 38 T[num][rt<<1|1].to_add(T[num][rt].add); 39 T[num][rt].init(); 40 } 41 void pushup(int num,int rt){ 42 T[num][rt].sum=T[num][rt<<1].sum+T[num][rt<<1|1].sum; 43 T[num][rt].maxn=max(T[num][rt<<1].maxn,T[num][rt<<1|1].maxn); 44 T[num][rt].minn=min(T[num][rt<<1].minn,T[num][rt<<1|1].minn); 45 } 46 void build(int num,int rt,int l,int r){ 47 T[num][rt].l=l; 48 T[num][rt].r=r; 49 T[num][rt].minn=T[num][rt].maxn=T[num][rt].sum=0; 50 T[num][rt].init(); 51 if(l==r){ 52 return; 53 } 54 int mid=T[num][rt].mid(); 55 build(num,rt<<1,l,mid); 56 build(num,rt<<1|1,mid+1,r); 57 pushup(num,rt); 58 } 59 void update(int num,int rt,int l,int r,int mul,int add){ 60 if(T[num][rt].l==l&&T[num][rt].r==r){ 61 T[num][rt].to_mul(mul); 62 T[num][rt].to_add(add); 63 return; 64 } 65 pushdown(num,rt); 66 int mid=T[num][rt].mid(); 67 if(mid>=r)update(num,rt<<1,l,r,mul,add); 68 else if(mid<l)update(num,rt<<1|1,l,r,mul,add); 69 else { 70 update(num,rt<<1,l,mid,mul,add); 71 update(num,rt<<1|1,mid+1,r,mul,add); 72 } 73 pushup(num,rt); 74 } 75 SegTree query(int num,int rt,int l,int r){ 76 if(T[num][rt].l==l&&T[num][rt].r==r) 77 return T[num][rt]; 78 pushdown(num,rt); 79 int mid=T[num][rt].mid(); 80 if(mid>=r)return query(num,rt<<1,l,r); 81 else if(mid<l)return query(num,rt<<1|1,l,r); 82 else{ 83 SegTree t1=query(num,rt<<1,l,mid); 84 SegTree t2=query(num,rt<<1|1,mid+1,r); 85 SegTree t; 86 t.maxn=max(t1.maxn,t2.maxn); 87 t.minn=min(t1.minn,t2.minn); 88 t.sum=t1.sum+t2.sum; 89 return t; 90 } 91 } 92 int n,m,r; 93 int x1,y1,x2,y2,val,type; 94 int main(){ 95 while(~scanf("%d%d%d",&r,&n,&m)){ 96 for(int i=1;i<=r;i++) 97 build(i,1,1,n); 98 for(int i=1;i<=m;i++){ 99 scanf("%d%d%d%d%d",&type,&x1,&y1,&x2,&y2); 100 if(type==1){ 101 scanf("%d",&val); 102 for(int i=x1;i<=x2;i++) 103 update(i,1,y1,y2,1,val); 104 } 105 else if(type==2){ 106 scanf("%d",&val); 107 for(int i=x1;i<=x2;i++) 108 update(i,1,y1,y2,0,val); 109 } 110 else { 111 int sum=0,minn=1000000002,maxn=0; 112 SegTree ans; 113 for(int i=x1;i<=x2;i++){ 114 ans=query(i,1,y1,y2); 115 sum+=ans.sum; 116 minn=min(minn,ans.minn); 117 maxn=max(maxn,ans.maxn); 118 } 119 printf("%d %d %d\n",sum,minn,maxn); 120 } 121 } 122 } 123 124 }
?
HDU 1885 Key Task BFS+狀態壓縮+水)
方法 源碼分析)
)
)
