线段树模板

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 1e6 + 10;
  4 struct node{
  5    int l, r, addv, setv, maxv, minv, sum;
  6 }e[maxn * 4];
  7 void bulid(int a, int b, int c){
  8    e[c].l = a, e[c].r = b;
  9    e[c].addv = e[c].setv = e[c].minv = e[c].maxv = e[c].sum = 0;
 10    if(a==b) return;
 11    int mid = (a+b)/2;
 12    bulid(a, mid, c*2);
 13    bulid(mid+1, b, c*2+1);
 14 }
 15 void pushdown(int c){
 16      int l = 2*c, r = 2*c+1;
 17    if(e[c].setv){
 18       e[l].addv = e[r].addv = 0;
 19       e[l].setv = e[r].setv = e[c].setv;
 20       e[l].minv = e[r].minv = e[c].setv;
 21       e[l].maxv = e[r].maxv = e[c].setv;
 22       e[l].sum  = (e[l].r - e[l].l + 1) * e[c].setv;
 23       e[r].sum  = (e[r].r - e[r].l + 1) * e[c].setv;
 24       e[c].setv = 0;
 25    }
 26    if(e[c].addv){
 27       e[l].addv += e[c].addv; e[r].addv += e[c].addv;
 28       e[l].maxv += e[c].addv; e[r].maxv += e[c].addv;
 29       e[l].minv += e[c].addv; e[r].minv += e[c].addv;
 30       e[l].sum += (e[l].r - e[l].l + 1) * e[c].addv;
 31       e[r].sum += (e[r].r - e[r].l + 1) * e[c].addv;
 32       e[c].addv = 0;
 33    }
 34 
 35 }
 36 void add(int a, int b, int c, int val){
 37    if(e[c].l == a && e[c].r == b){
 38     e[c].addv += val;
 39     e[c].maxv += val;
 40     e[c].minv += val;
 41     e[c].sum += (b-a+1)*val;
 42     return;
 43    }
 44    int mid = (e[c].l + e[c].r) / 2;
 45    pushdown(c);
 46    if(b <= mid) add(a, b, 2*c, val);
 47    else if(a > mid) add(a, b, 2*c+1, val);
 48    else{
 49        add(a, mid, 2*c, val);
 50        add(mid+1, b, 2*c+1, val);
 51    }
 52    e[c].maxv = max(e[c*2].maxv, e[c*2+1].maxv);
 53    e[c].minv = min(e[c*2].minv, e[c*2+1].minv);
 54    e[c].sum = e[2*c].sum + e[2*c+1].sum;
 55 
 56 }
 57 void update(int a, int b, int c, int val){
 58    if(e[c].l == a && e[c].r == b){
 59     e[c].addv = 0;
 60     e[c].setv = val;
 61     e[c].maxv = val;
 62     e[c].minv = val;
 63     e[c].sum = (b-a+1)*val;
 64     return;
 65    }
 66    pushdown(c);
 67    int mid = (e[c].l + e[c].r) / 2;
 68    if(b <= mid) update(a, b, 2*c, val);
 69    else if(a > mid) update(a, b, 2*c+1, val);
 70    else{
 71     update(a, mid, 2*c, val);
 72     update(mid+1, b, 2*c+1, val);
 73    }
 74    e[c].maxv = max(e[c*2].maxv, e[c*2+1].maxv);
 75    e[c].minv = min(e[c*2].minv, e[c*2+1].minv);
 76    e[c].sum = e[2*c].sum + e[2*c+1].sum;
 77 }
 78 node query(int a, int b, int c){
 79    if(e[c].l == a && e[c].r == b) return e[c];
 80    pushdown(c);
 81    int mid = (e[c].l + e[c].r) / 2;
 82    if(b <= mid) return query(a, b, 2*c);
 83    else if(a > mid) return query(a, b, 2*c+1);
 84    else{
 85     node o, p, q;
 86     p = query(a, mid, 2*c);
 87     q = query(mid + 1, b, 2*c+1);
 88     o.sum = p.sum + q.sum;
 89     o.maxv = max(p.maxv, q.maxv);
 90     o.minv = min(p.minv, q.minv);
 91     return o;
 92    }
 93 
 94 }
 95 int main()
 96 {
 97     ios::sync_with_stdio(false);
 98     int r, c, m;
 99     while(cin >> r >> c >> m){
100     int i, j, k ,a, x1, y1, x2, y2, val;
101     bulid(1, r * c, 1);
102     for(i = 0; i < m; i++){
103         cin >> a;
104         if(a==1){
105             cin >> x1 >> y1 >> x2 >> y2 >> val;
106             for(j = x1; j <= x2; j++)
107                 add((j-1)*c+y1, (j-1)*c+y2, 1, val);
108         } else if(a==2){
109             cin >> x1 >> y1 >> x2 >> y2 >> val;
110             for(j = x1; j <= x2; j++)
111                 update((j-1)*c+y1, (j-1)*c+y2, 1, val);
112         }else{
113             node ans, p;
114             cin >> x1 >> y1 >> x2 >> y2;
115             for(j = x1; j <= x2; j++){
116                 if(j==x1) ans = query((j-1)*c+y1, (j-1)*c+y2, 1);
117                 else{
118                     p = query((j-1)*c+y1, (j-1)*c+y2, 1);
119                     ans.sum += p.sum;
120                     ans.maxv = max(ans.maxv, p.maxv);
121                     ans.minv = min(ans.minv, p.minv);
122                 }
123 
124             }
125             cout << ans.sum << " " << ans.minv << " " << ans.maxv << endl;
126 
127         }
128 
129 
130     }
131     }
132 }