首页 > 代码库 > UVA 11992 Fast Matrix Operations

UVA 11992 Fast Matrix Operations

线段树

 

 

  1 #include <iostream>  2 using namespace std;  3   4 const int maxn = 1000005;  5 const int INF = 1000000009;  6   7 struct node {  8     int sum,ma,mi;  9     int addv,setv; 10     void init (int nsum,int nma,int nmi,int naddv,int nsetv){ 11         sum=nsum;ma=nma;mi=nmi; 12         addv=naddv;setv=nsetv; 13     } 14 }tree[30][maxn*2]; 15  16 int r,c,m; 17  18 void init (){ 19     for (int i=1;i<=r;i++){ 20         for (int j=1;j<=c*2;j++){ 21             tree[i][j].init (0,0,0,0,-1); 22         } 23         tree[i][1].setv=0; 24     } 25 } 26  27 //int sum[30][maxn],ma[30][maxn],mi[30][maxn]; 28 //int addv[30][maxn],setv[30][maxn]; 29  30 void maintain (int o,int l,int r,int i){ 31     int lc=o<<1,rc=(o<<1)+1; 32     if (r>l){ 33         tree[i][o].sum=tree[i][lc].sum+tree[i][rc].sum; 34         tree[i][o].mi=min (tree[i][lc].mi,tree[i][rc].mi); 35         tree[i][o].ma=max (tree[i][lc].ma,tree[i][rc].ma); 36     } 37         if (tree[i][o].setv!=-1){ 38             tree[i][o].mi=tree[i][o].setv; 39             tree[i][o].ma=tree[i][o].setv; 40             tree[i][o].sum=tree[i][o].setv*(r-l+1); 41         } 42         if (tree[i][o].addv){ 43             tree[i][o].mi+=tree[i][o].addv; 44             tree[i][o].ma+=tree[i][o].addv; 45             tree[i][o].sum+=tree[i][o].addv*(r-l+1); 46         } 47 } 48  49 void pushdown (int o,int i){ 50     int lc=o<<1,rc=(o<<1)+1; 51     if (tree[i][o].setv!=-1){ 52         tree[i][lc].setv=tree[i][rc].setv=tree[i][o].setv; 53         tree[i][lc].addv=tree[i][rc].addv=0; 54         tree[i][o].setv=-1; 55     } 56     if (tree[i][o].addv>0){ 57         tree[i][lc].addv+=tree[i][o].addv; 58         tree[i][rc].addv+=tree[i][o].addv; 59         tree[i][o].addv=0; 60     } 61 } 62  63 void add (int o,int l,int r,int x1,int x2,int i,int v){ 64     int m=l+(r-l)/2,lc=o<<1,rc=(o<<1)+1; 65     if (x1<=l&&r<=x2){ 66         tree[i][o].addv+=v; 67     } 68     else { 69         pushdown (o,i); 70         if (x1<=m) add (lc,l,m,x1,x2,i,v);else maintain (lc,l,m,i); 71         if (m<x2) add (rc,m+1,r,x1,x2,i,v);else maintain (rc,m+1,r,i); 72     } 73     maintain (o,l,r,i); 74     return ; 75 } 76  77 void set (int o,int l,int r,int x1,int x2,int i,int v){ 78     int m=l+(r-l)/2; 79     int lc=o<<1,rc=(o<<1)+1; 80     if (x1<=l&&r<=x2){ 81         tree[i][o].setv=v; 82         tree[i][o].addv=0; 83     } 84     else { 85         pushdown (o,i); 86     if (x1<=m) set (lc,l,m,x1,x2,i,v);else maintain (lc,l,m,i); 87     if (m<x2) set (rc,m+1,r,x1,x2,i,v);else maintain (rc,m+1,r,i); 88     } 89     maintain (o,l,r,i); 90     return ; 91 } 92 int sum,ma,mi; 93 int query (int o,int l,int r,int x1,int x2,int i,int addv){ 94     int m=l+(r-l)/2,lc=o<<1,rc=(o<<1)+1; 95     if (tree[i][o].setv!=-1){ 96         int x=tree[i][o].setv+addv+tree[i][o].addv; 97         sum+=x*(min(r,x2)-max(l,x1)+1); 98         mi=min (mi,x); 99         ma=max (ma,x);100         addv=0;101     }102     else if (x1<=l&&r<=x2){103         sum+=tree[i][o].sum+addv*(r-l+1);104         mi=min (mi,tree[i][o].mi+addv);105         ma=max (ma,tree[i][o].ma+addv);106     }107     else {108         if (x1<=m) query (lc,l,m,x1,x2,i,addv+tree[i][o].addv);109         if (x2>m) query (rc,m+1,r,x1,x2,i,addv+tree[i][o].addv);110     }111 }112 113 int main (){114     while (cin>>r>>c>>m){115         init ();116         while (m--){117             int f,x1,x2,y1,y2,v;118             cin>>f>>x1>>y1>>x2>>y2;119             if (f==1){120                 cin>>v;121                 for (int i=x1;i<=x2;i++)122                     add (1,1,c,y1,y2,i,v);123             }124             else if (f==2){125                 cin>>v;126                 for (int i=x1;i<=x2;i++)127                     set (1,1,c,y1,y2,i,v);128             }129             else if (f==3){130                 sum=0;ma=-INF;mi=INF;131                 for (int i=x1;i<=x2;i++)132                     query (1,1,c,y1,y2,i,0);133                 cout<<sum<<" "<<mi<<" "<<ma<<endl;134             }135         }136     }137     return 0;138 }