台州服务网站,怎么做网页?,免费开拼多多网店,小程序自己免费制作uva11992:http://uva.onlinejudge.org/index.php?optioncom_onlinejudgeItemid8pageshow_problemproblem3143 题意#xff1a;给你n*m的矩阵初始化的时候矩阵里面的元素全部是0#xff0c;对于这个矩阵有3中操作。 1 x1 y1 x2 y2 v 把#xff08;x1 y1 x2…uva11992:http://uva.onlinejudge.org/index.php?optioncom_onlinejudgeItemid8pageshow_problemproblem3143 题意给你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可以看成是*0v加上v可以看成*1v 线段树维护一个mul乘数add加数sum总和minn最小值maxn最大值。注意pushdown时候对子节点先*后加。 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includecstring5 using namespace std;6 const int N100002;7 struct SegTree{8 int l,r;9 int add,mul;10 int sum,minn,maxn;11 void init(){12 add0;mul1;13 }14 inline int mid(){15 return (lr) 1;16 }17 inline int len(){18 return r-l1;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 minna;29 maxna;30 sum a* len();31 add a;32 }33 }T[23][N*4];34 void pushdown(int num,int rt){//这里一定要注意35 T[num][rt1].to_mul(T[num][rt].mul);36 T[num][rt1|1].to_mul(T[num][rt].mul);37 T[num][rt1].to_add(T[num][rt].add);38 T[num][rt1|1].to_add(T[num][rt].add);39 T[num][rt].init();40 }41 void pushup(int num,int rt){42 T[num][rt].sumT[num][rt1].sumT[num][rt1|1].sum;43 T[num][rt].maxnmax(T[num][rt1].maxn,T[num][rt1|1].maxn);44 T[num][rt].minnmin(T[num][rt1].minn,T[num][rt1|1].minn);45 }46 void build(int num,int rt,int l,int r){47 T[num][rt].ll;48 T[num][rt].rr;49 T[num][rt].minnT[num][rt].maxnT[num][rt].sum0;50 T[num][rt].init();51 if(lr){52 return;53 }54 int midT[num][rt].mid();55 build(num,rt1,l,mid);56 build(num,rt1|1,mid1,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].llT[num][rt].rr){61 T[num][rt].to_mul(mul);62 T[num][rt].to_add(add);63 return;64 }65 pushdown(num,rt);66 int midT[num][rt].mid();67 if(midr)update(num,rt1,l,r,mul,add);68 else if(midl)update(num,rt1|1,l,r,mul,add);69 else {70 update(num,rt1,l,mid,mul,add);71 update(num,rt1|1,mid1,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].llT[num][rt].rr)77 return T[num][rt];78 pushdown(num,rt);79 int midT[num][rt].mid();80 if(midr)return query(num,rt1,l,r);81 else if(midl)return query(num,rt1|1,l,r);82 else{83 SegTree t1query(num,rt1,l,mid);84 SegTree t2query(num,rt1|1,mid1,r);85 SegTree t;86 t.maxnmax(t1.maxn,t2.maxn);87 t.minnmin(t1.minn,t2.minn);88 t.sumt1.sumt2.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 i1;ir;i)97 build(i,1,1,n);98 for(int i1;im;i){99 scanf(%d%d%d%d%d,type,x1,y1,x2,y2);
100 if(type1){
101 scanf(%d,val);
102 for(int ix1;ix2;i)
103 update(i,1,y1,y2,1,val);
104 }
105 else if(type2){
106 scanf(%d,val);
107 for(int ix1;ix2;i)
108 update(i,1,y1,y2,0,val);
109 }
110 else {
111 int sum0,minn1000000002,maxn0;
112 SegTree ans;
113 for(int ix1;ix2;i){
114 ansquery(i,1,y1,y2);
115 sumans.sum;
116 minnmin(minn,ans.minn);
117 maxnmax(maxn,ans.maxn);
118 }
119 printf(%d %d %d\n,sum,minn,maxn);
120 }
121 }
122 }
123
124 } View Code 转载于:https://www.cnblogs.com/chujian123/p/3840487.html
