主体段树，要注意，因为有set和add操作，当慵懒的标志下推。递归优先set，后复发add，每次运行set行动add马克清0
WA了好几次是由于计算那一段的时候出问题了，可笑的是我对着模板找了一个多小时的错。
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
#define lson pos << 1
#define rson pos << 1|1
typedef unsigned long long ULL;
typedef long long LL;
const int maxn = 1111111;
const int INF = 1 << 30;
struct Node{int left,right;int max_value,min_value,sum_value;int col;int col2;
}tr[maxn << 2];
struct Ans{int min_value;int max_value;int sum_value;Ans(int a = INF,int b = 0,int c = 0):min_value(a),max_value(b),sum_value(c){};
};
int n,m,k;
void pushdown(int pos){if(tr[pos].col){int len1 = tr[lson].right - tr[lson].left + 1;int len2 = tr[rson].right - tr[rson].left + 1;tr[lson].sum_value += (tr[pos].col * len1);tr[lson].max_value += tr[pos].col;tr[lson].min_value += tr[pos].col;tr[rson].sum_value += (tr[pos].col * len2);tr[rson].max_value += tr[pos].col;tr[rson].min_value += tr[pos].col;tr[lson].col += tr[pos].col;tr[rson].col += tr[pos].col;tr[pos].col = 0;}return ;
}
void pushdown2(int pos){if(tr[pos].col2 >= 0){int len1 = tr[lson].right - tr[lson].left + 1;int len2 = tr[rson].right - tr[rson].left + 1;tr[lson].sum_value = (tr[pos].col2 * len1);tr[lson].max_value = tr[pos].col2;tr[lson].min_value = tr[pos].col2;tr[rson].sum_value = (tr[pos].col2 * len2);tr[rson].max_value = tr[pos].col2;tr[rson].min_value = tr[pos].col2;tr[lson].col2 = tr[pos].col2; tr[lson].col = 0; //set递推须要清空求和tr[rson].col2 = tr[pos].col2; tr[rson].col = 0;tr[pos].col2 = -1;}return ;
}
void pushup(int pos){tr[pos].sum_value = tr[lson].sum_value + tr[rson].sum_value;tr[pos].max_value = max(tr[lson].max_value,tr[rson].max_value);tr[pos].min_value = min(tr[lson].min_value,tr[rson].min_value);return ;
}
void BuildTree(int L,int R,int pos){tr[pos].left = L; tr[pos].right = R; tr[pos].col = 0;tr[pos].col2 = -1;tr[pos].max_value = 0; tr[pos].min_value = 0; tr[pos].sum_value = 0;if(L == R) return ;int m = (L + R) >> 1;BuildTree(L,m,lson);BuildTree(m + 1,R,rson);return ;
}
void TreeAdd(int l,int r,int add,int pos){if(l <= tr[pos].left && tr[pos].right <= r){int len = tr[pos].right - tr[pos].left + 1;tr[pos].max_value += add; tr[pos].min_value += add;tr[pos].sum_value += (add * len); tr[pos].col += add;return ;}pushdown2(pos);pushdown(pos);int m = (tr[pos].left + tr[pos].right) >> 1;if(l <= m)TreeAdd(l,r,add,lson);if(r > m)TreeAdd(l,r,add,rson);pushup(pos);
}
void TreeSet(int l,int r,int value,int pos){if(l <= tr[pos].left && tr[pos].right <= r){int len = tr[pos].right - tr[pos].left + 1;tr[pos].max_value = value; tr[pos].min_value = value;tr[pos].sum_value = (value * len); tr[pos].col2 = value;tr[pos].col = 0;return ;}pushdown2(pos);pushdown(pos);int m = (tr[pos].left + tr[pos].right) >> 1;if(l <= m)TreeSet(l,r,value,lson);if(r > m)TreeSet(l,r,value,rson);pushup(pos);
}
Ans Query(int l,int r,int pos){if(l <= tr[pos].left && tr[pos].right <= r){return Ans(tr[pos].min_value,tr[pos].max_value,tr[pos].sum_value);}pushdown2(pos);pushdown(pos);int m = (tr[pos].left + tr[pos].right) >> 1;Ans a,b;if(l <= m)a = Query(l,r,lson);if(r > m)b = Query(l,r,rson);pushup(pos);return Ans(min(a.min_value,b.min_value),max(a.max_value,b.max_value),a.sum_value + b.sum_value);
}
int main(){while(scanf("%d%d%d",&n,&m,&k) != EOF){BuildTree(1,n * m,1);while(k--){int t;scanf("%d",&t);if(t == 1){int x1,y1,x2,y2,v;//addscanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);for(int i = x1 ; i <= x2 ; i++){int l = (i - 1) * m + y1;int r = (i - 1) * m + y2;TreeAdd(l,r,v,1);}}else if(t == 2){int x1,y1,x2,y2,v;//addscanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);for(int i = x1 ; i <= x2 ; i++){int l = (i - 1) * m + y1;int r = (i - 1) * m + y2;TreeSet(l,r,v,1);}}else if(t == 3){int x1,y1,x2,y2;Ans t;int MAX = 0,MIN = INF,SUM = 0;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(int i = x1 ; i <= x2 ; i++){int l = (i - 1) * m + y1;int r = (i - 1) * m + y2;t = Query(l,r,1);SUM += t.sum_value;MAX = max(MAX,t.max_value);MIN = min(MIN,t.min_value);}printf("%d %d %d\n",SUM,MIN,MAX);}}}return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
