BZOJ 1452：[JSOI2009]Count（二维树状数组）

[JSOI2009]Count

描述

输入

输出

1
2

分析：

裸二维bit，对每个颜色建一颗bit。

program count;

var

  bit:array[..,..,..]of longint;

  a:array[..,..]of longint;

  n,i,m,j,x,y,c,x1,y1,x2,y2,q,g,ans:longint;

procedure add(x,y,c,v:longint);

var i:longint;

begin

  i:=y;

  while x<=n do

   begin

     while y<=m do begin inc(bit[c,x,y],v); y:=y+y and (-y); end;

     x:=x+x and (-x); y:=i;

   end;

end;

function ask(x,y,c:longint):longint;

var i,s:longint;

begin

  i:=y; s:=;

  while x> do

   begin

     while y> do begin inc(s,bit[c,x,y]); y:=y-y and (-y); end;

     x:=x-x and (-x); y:=i;

   end;

  exit(s);

end;

begin

  readln(n,m);

  for i:= to n do begin

   for j:= to m do

     begin

       read(c); add(i,j,c,); a[i,j]:=c;

     end;

   readln;

  end;

  readln(q);

  for i:= to q do

   begin

     read(g);

     if g= then

      begin

        read(x,y,c); add(x,y,a[x,y],-); a[x,y]:=c;  add(x,y,c,);

      end

     else

     begin

      read(x1,x2,y1,y2,c);

      ans:=ask(x2,y2,c)+ask(x1-,y1-,c)-ask(x1-,y2,c)-ask(x2,y1-,c);

      writeln(ans);

     end;

     readln;

   end;

end.