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 }