首页 > 代码库 > Fast Matrix Operations(UVA)11992
Fast Matrix Operations(UVA)11992
UVA 11992 - Fast Matrix Operations
给定一个r*c(r<=20,r*c<=1e6)的矩阵，其元素都是0，现在对其子矩阵进行操作。
1 x1 y1 x2 y2 val 表示将(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素add上val；
2 x1 y1 x2 y2 val 表示将(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素set为val；
3 x1 y1 x2 y2 val 表示输出(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩阵中的所有元素的sum，最大最小值max,min;
思路：线段树区间更新+lazy
每行维护一个线段树，然后，线段树维护四个值，max，min,sum，set，add。如果当前set，add都有值，那么先操作set再add,复杂度(n*log(n));
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<stack> 7 #include<math.h> 8 using namespace std; 9 typedef long long LL; 10 typedef struct node 11 { 12 int addv; 13 int setv; 14 int maxx; 15 int minn; 16 int sum; 17 int l; 18 int r; 19 node() 20 { 21 addv = 0; 22 setv = 0; 23 maxx = 0; 24 sum = 0; 25 } 26 } tr; 27 tr tree[30][100005*8]; 28 tr flag[100005*8]; 29 void build(int l,int r,int k); 30 void update(int k,int id); 31 void add(int l,int r,int k,int nn,int mm,int id,int a); 32 void sett(int l,int r,int k,int nn,int mm,int id,int a); 33 int asksum(int l,int r,int k,int nn,int mm,int id); 34 int askminn(int l,int r,int k,int nn,int mm,int id); 35 int askmaxx(int l,int r,int k,int nn,int mm,int id); 36 int main(void) 37 { 38 int n,m,q; 39 while(scanf("%d %d %d",&n,&m,&q)!=EOF) 40 { memset(tree,0,sizeof(tree)); 41 memset(flag,0,sizeof(flag));build(1,m,0); 42 while(q--) 43 { 44 int val ; 45 scanf("%d",&val); 46 if(val == 1) 47 { 48 int x1,y1,x2,y2,v; 49 scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&v); 50 int i,j; 51 for(i = x1;i <= x2;i++) 52 { 53 add(y1,y2,0,1,m,i,v); 54 } 55 } 56 else if(val == 2) 57 { 58 int x1,y1,x2,y2,v;int i,j; 59 scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&v); 60 for(i = x1;i <= x2;i++) 61 { 62 sett(y1,y2,0,1,m,i,v); 63 } 64 } 65 else 66 { 67 int x1,y1,x2,y2;int i,j; 68 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 69 int su = 0;int ma = 0;int mi = 1e9; 70 for(i = x1;i <= x2;i++) 71 { 72 su += asksum(y1,y2,0,1,m,i); 73 ma = max(askmaxx(y1,y2,0,1,m,i),ma); 74 mi = min(mi,askminn(y1,y2,0,1,m,i)); 75 } 76 printf("%d %d %d\n",su,mi,ma); 77 } 78 } 79 } 80 return 0; 81 } 82 void build(int l,int r,int k) 83 { 84 if(l == r) 85 { 86 flag[k].l = l; 87 flag[k].r = r; 88 return ; 89 } 90 else 91 { 92 flag[k].l = l; 93 flag[k].r = r; 94 build(l,(l+r)/2,2*k+1); 95 build((l+r)/2+1,r,2*k+2); 96 } 97 } 98 void update(int k,int id) 99 {100 while(k>0)101 {102 k = (k-1)/2;103 int x1 = 2*k+1;104 int x2 = 2*k+2;105 if(tree[id][x1].setv)106 { //printf("1\n");107 int xx1 = x1;108 tree[id][2*xx1+1].setv = tree[id][x1].setv;109 tree[id][2*xx1+2].setv = tree[id][x1].setv;110 tree[id][2*xx1+1].addv = tree[id][x1].addv;111 tree[id][2*xx1+2].addv = tree[id][x1].addv;112 tree[id][x1].maxx = tree[id][x1].setv + tree[id][x1].addv;113 tree[id][x1].minn = tree[id][x1].setv + tree[id][x1].addv;114 tree[id][x1].sum = tree[id][x1].maxx*(flag[x1].r-flag[x1].l+1);115 tree[id][x1].setv = 0;116 tree[id][x1].addv = 0;117 }118 else if(tree[id][x1].addv)119 {120 int xx1 = x1;121 tree[id][2*xx1+1].addv += tree[id][x1].addv;122 tree[id][2*xx1+2].addv += tree[id][x1].addv;123 tree[id][x1].maxx = tree[id][x1].maxx + tree[id][x1].addv;124 tree[id][x1].minn = tree[id][x1].minn + tree[id][x1].addv;125 tree[id][x1].sum += (flag[x1].r-flag[x1].l+1)*(tree[id][x1].addv);126 tree[id][x1].setv = 0;127 tree[id][x1].addv = 0;128 }129 if(tree[id][x2].setv)130 {131 int xx1 = x2;132 tree[id][2*xx1+1].setv = tree[id][x2].setv;133 tree[id][2*xx1+2].setv = tree[id][x2].setv;134 tree[id][2*xx1+1].addv = tree[id][x2].addv;135 tree[id][2*xx1+2].addv = tree[id][x2].addv;136 tree[id][x2].maxx = tree[id][x2].setv + tree[id][x2].addv;137 tree[id][x2].minn = tree[id][x2].setv + tree[id][x2].addv;138 tree[id][x2].sum = tree[id][x2].maxx*(flag[x2].r-flag[x2].l+1);139 tree[id][x2].setv = 0;140 tree[id][x2].addv = 0;141 }142 else if(tree[id][x2].addv)143 { //printf("%d\n",1);144 int xx1 = x2;145 tree[id][2*xx1+1].addv += tree[id][x2].addv;146 tree[id][2*xx1+2].addv += tree[id][x2].addv;147 tree[id][x2].maxx = tree[id][x2].maxx + tree[id][x2].addv;148 tree[id][x2].minn = tree[id][x2].minn + tree[id][x2].addv;149 tree[id][x2].sum += (flag[x2].r-flag[x2].l+1)*(tree[id][x2].addv);150 tree[id][x2].setv = 0;151 tree[id][x2].addv = 0;152 }153 tree[id][k].maxx = max(tree[id][x1].maxx,tree[id][x2].maxx);154 tree[id][k].minn = min(tree[id][x1].minn,tree[id][x2].minn);155 tree[id][k].sum = tree[id][x1].sum+tree[id][x2].sum;156 }157 }158 void add(int l,int r,int k,int nn,int mm,int id,int a)159 {160 if(l > mm||r < nn)161 return ;162 else if(l <= nn&&r >= mm)163 {164 tree[id][k].addv += a;165 if(tree[id][k].setv )166 {167 tree[id][2*k+1].setv = tree[id][k].setv;168 tree[id][2*k+2].setv = tree[id][k].setv;169 tree[id][2*k+1].addv = tree[id][k].addv;170 tree[id][2*k+2].addv = tree[id][k].addv;171 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);172 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;173 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;174 tree[id][k].setv = 0;175 tree[id][k].addv = 0;176 // update(k,id);177 }178 else179 {180 tree[id][2*k+1].addv += tree[id][k].addv;181 tree[id][2*k+2].addv += tree[id][k].addv;182 //printf("%d\n",tree[id][2*k+1].addv);183 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;184 tree[id][k].maxx += tree[id][k].addv;185 tree[id][k].minn += tree[id][k].addv;186 tree[id][k].addv = 0;187 //printf("%d\n",tree[id][k].sum);188 }189 update(k,id);190 }191 else192 {193 if(tree[id][k].setv)194 {195 tree[id][2*k+1].setv = tree[id][k].setv;196 tree[id][2*k+2].setv = tree[id][k].setv;197 tree[id][2*k+1].addv = tree[id][k].addv;198 tree[id][2*k+2].addv = tree[id][k].addv;199 tree[id][k].setv = 0;200 tree[id][k].addv = 0;201 }202 else if(tree[id][k].addv)203 {204 tree[id][2*k+1].addv += tree[id][k].addv ;205 tree[id][2*k+2].addv += tree[id][k].addv;206 tree[id][k].addv = 0;207 }208 add(l,r,2*k+1,nn,(nn+mm)/2,id,a);209 add(l,r,2*k+2,(nn+mm)/2+1,mm,id,a);210 }211 }212 void sett(int l,int r,int k,int nn,int mm,int id,int a)213 {214 if(l > mm||r < nn)215 return ;216 else if(l <= nn&&r >= mm)217 {218 tree[id][k].setv = a;219 if(tree[id][k].setv != 0)220 {221 tree[id][k].addv = 0;222 tree[id][2*k+1].setv = tree[id][k].setv;223 tree[id][2*k+2].setv = tree[id][k].setv;224 tree[id][2*k+1].addv = tree[id][k].addv;225 tree[id][2*k+2].addv = tree[id][k].addv;226 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);227 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;228 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;229 tree[id][k].setv = 0;230 tree[id][k].addv = 0;231 }232 update(k,id);233 }234 else235 {236 if(tree[id][k].setv)237 {238 tree[id][2*k+1].setv = tree[id][k].setv;239 tree[id][2*k+2].setv = tree[id][k].setv;240 tree[id][2*k+1].addv = tree[id][k].addv;241 tree[id][2*k+2].addv = tree[id][k].addv;242 tree[id][k].setv = 0;243 tree[id][k].addv = 0;244 }245 else if(tree[id][k].addv)246 {247 tree[id][2*k+1].addv += tree[id][k].addv ;248 tree[id][2*k+2].addv += tree[id][k].addv;249 tree[id][k].addv = 0;250 }251 sett(l,r,2*k+1,nn,(nn+mm)/2,id,a);252 sett(l,r,2*k+2,(nn+mm)/2+1,mm,id,a);253 }254 }255 int asksum(int l,int r,int k,int nn,int mm,int id)256 {257 if(l>mm||r<nn)258 return 0;259 else if(l <= nn&&r>=mm)260 { //printf("%d %d\n",id,k);261 if(tree[id][k].setv )262 {263 tree[id][2*k+1].setv = tree[id][k].setv;264 tree[id][2*k+2].setv = tree[id][k].setv;265 tree[id][2*k+1].addv = tree[id][k].addv;266 tree[id][2*k+2].addv = tree[id][k].addv;267 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);268 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;269 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;270 tree[id][k].setv = 0;271 tree[id][k].addv = 0; update(k,id);272 }273 else if(tree[id][k].addv)274 {275 tree[id][2*k+1].addv += tree[id][k].addv;276 tree[id][2*k+2].addv += tree[id][k].addv;277 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;278 tree[id][k].maxx += tree[id][k].addv;279 tree[id][k].minn += tree[id][k].addv;280 tree[id][k].addv = 0; update(k,id);281 }282 return tree[id][k].sum;283 }284 else285 {286 if(tree[id][k].setv)287 {288 tree[id][2*k+1].setv = tree[id][k].setv;289 tree[id][2*k+2].setv = tree[id][k].setv;290 tree[id][2*k+1].addv = tree[id][k].addv;291 tree[id][2*k+2].addv = tree[id][k].addv;292 tree[id][k].setv = 0;293 tree[id][k].addv = 0;294 }295 else if(tree[id][k].addv)296 {297 tree[id][2*k+1].addv += tree[id][k].addv ;298 tree[id][2*k+2].addv += tree[id][k].addv;299 tree[id][k].addv = 0;300 }301 int nx = asksum(l,r,2*k+1,nn,(nn+mm)/2,id);302 int ny = asksum(l,r,2*k+2,(nn+mm)/2+1,mm,id);303 return nx+ny;304 }305 306 }307 int askminn(int l,int r,int k,int nn,int mm,int id)308 {309 if(l>mm||r<nn)310 return 1e9;311 else if(l <= nn&&r>=mm)312 {313 if(tree[id][k].setv != 0)314 {315 tree[id][2*k+1].setv = tree[id][k].setv;316 tree[id][2*k+2].setv = tree[id][k].setv;317 tree[id][2*k+1].addv = tree[id][k].addv;318 tree[id][2*k+2].addv = tree[id][k].addv;319 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);320 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;321 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;322 tree[id][k].setv = 0;323 tree[id][k].addv = 0; update(k,id);324 }325 else if(tree[id][k].addv)326 {327 tree[id][2*k+1].addv += tree[id][k].addv;328 tree[id][2*k+2].addv += tree[id][k].addv;329 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;330 tree[id][k].maxx += tree[id][k].addv;331 tree[id][k].minn += tree[id][k].addv;332 tree[id][k].addv = 0; update(k,id);333 }334 // update(k,id);335 return tree[id][k].minn;336 }337 else338 {339 if(tree[id][k].setv)340 {341 tree[id][2*k+1].setv = tree[id][k].setv;342 tree[id][2*k+2].setv = tree[id][k].setv;343 tree[id][2*k+1].addv = tree[id][k].addv;344 tree[id][2*k+2].addv = tree[id][k].addv;345 tree[id][k].setv = 0;346 tree[id][k].addv = 0;347 }348 else if(tree[id][k].addv)349 {350 tree[id][2*k+1].addv += tree[id][k].addv ;351 tree[id][2*k+2].addv += tree[id][k].addv;352 tree[id][k].addv = 0;353 }354 int nx = askminn(l,r,2*k+1,nn,(nn+mm)/2,id);355 int ny = askminn(l,r,2*k+2,(nn+mm)/2+1,mm,id);356 return min(nx,ny);357 }358 }359 int askmaxx(int l,int r,int k,int nn,int mm,int id)360 {361 if(l>mm||r<nn)362 return 0;363 else if(l <= nn&&r>=mm)364 {365 if(tree[id][k].setv != 0)366 {367 tree[id][2*k+1].setv = tree[id][k].setv;368 tree[id][2*k+2].setv = tree[id][k].setv;369 tree[id][2*k+1].addv = tree[id][k].addv;370 tree[id][2*k+2].addv = tree[id][k].addv;371 tree[id][k].sum = (tree[id][k].setv + tree[id][k].addv)*(mm-nn+1);372 tree[id][k].maxx = tree[id][k].setv + tree[id][k].addv;373 tree[id][k].minn = tree[id][k].setv + tree[id][k].addv;374 tree[id][k].setv = 0;375 tree[id][k].addv = 0; update(k,id);376 }377 else if(tree[id][k].addv)378 {379 tree[id][2*k+1].addv += tree[id][k].addv;380 tree[id][2*k+2].addv += tree[id][k].addv;381 tree[id][k].sum += (mm-nn+1)*tree[id][k].addv;382 tree[id][k].maxx += tree[id][k].addv;383 tree[id][k].minn += tree[id][k].addv;384 tree[id][k].addv = 0; update(k,id);385 }386 //update(k,id);387 return tree[id][k].maxx;388 }389 else390 {391 if(tree[id][k].setv)392 {393 tree[id][2*k+1].setv = tree[id][k].setv;394 tree[id][2*k+2].setv = tree[id][k].setv;395 tree[id][2*k+1].addv = tree[id][k].addv;396 tree[id][2*k+2].addv = tree[id][k].addv;397 tree[id][k].setv = 0;398 tree[id][k].addv = 0;399 }400 else if(tree[id][k].addv)401 {402 tree[id][2*k+1].addv += tree[id][k].addv ;403 tree[id][2*k+2].addv += tree[id][k].addv;404 tree[id][k].addv = 0;405 }406 int nx = askmaxx(l,r,2*k+1,nn,(nn+mm)/2,id);407 int ny = askmaxx(l,r,2*k+2,(nn+mm)/2+1,mm,id);408 return max(nx,ny);409 }410 }
Fast Matrix Operations(UVA)11992
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。