首页 > 代码库 > BZOJ1452 count (树状数组)

BZOJ1452 count (树状数组)

一道比较水的二维树状数组,开100个即可,只有100种颜色还是比较EZ的。

 1 Program BZOJ1452; 2 const maxn=308; 3       maxc=108; 4 var a:array[0..maxn,0..maxn,0..maxc] of longint; 5     f:array[0..maxn,0..maxn] of longint; 6     m,n,i,j,x,y,x1,y1,x2,y2,z,Q,ch,sum:longint; 7 procedure add(i,j,c,k:longint); 8 var x,y:longint; 9 begin10     x:=i;11     while x<=m do12     begin13         y:=j;14         while y<=n do15         begin16             inc(a[x,y,c],k);17             y:=y+y and -y;18         end;19         x:=x+x and -x;20     end;21 end;22 function sigma(i,j,c:longint):longint;23 var x,y,sum:longint;24 begin25     sum:=0;    x:=i;26     while x>0 do27     begin28         y:=j;29         while y>0 do30         begin31             inc(sum,a[x,y,c]);32             y:=y-y and -y;33         end;34         x:=x-x and -x;35     end;36     exit(sum);37 end;38 begin39     readln(m,n);40     for i:=1 to m do41         for j:=1 to n do42         begin43             read(x);44             add(i,j,x,1);45             f[i,j]:=x;46         end;47     readln(Q);48     while Q>0 do49     begin50         read(ch);51         if ch=1 then52         begin53             readln(x,y,z);54             add(x,y,f[x,y],-1);55             f[x,y]:=z;56             add(x,y,z,1);        57         end else58         begin59             readln(x1,x2,y1,y2,z);60             sum:=sigma(x2,y2,z)-sigma(x1-1,y2,z)-sigma(x2,y1-1,z)+sigma(x1-1,y1-1,z);        61             writeln(sum);62         end;63         dec(Q);64     end;65 end.

 

BZOJ1452 count (树状数组)