bzoj1452 二维树状数组

 1 program hehe;
 2 var
 3  n,m,i,j,q,x1,y1,x2,y2,co:longint;
 4  y:array[0..300,0..300] of longint;
 5  x:array[0..100,0..300,0..300] of longint;
 6 
 7   procedure add(k,a,b,t:longint);
 8   var
 9    c:longint;
10   begin
11    while a<=n do
12    begin
13     c:=b;
14     while c<=m do
15     begin
16      x[k,a,c]:=x[k,a,c]+t;
17      c:=c+(c and(-c));
18     end;
19     a:=a+(a and(-a));
20    end;
21   end;
22 
23   function find(k,a,b:longint):longint;
24   var
25    s,c:longint;
26   begin
27    s:=0;
28    while a>0 do
29    begin
30     c:=b;
31     while c>0 do
32     begin
33      s:=s+x[k,a,c];
34      c:=c-(c and(-c));
35     end;
36     a:=a-(a and(-a));
37    end;
38    exit(s);
39   end;
40 
41 begin
42  readln(n,m);
43  for i:=1 to n do
44  for j:=1 to m do
45  begin
46   read(y[i,j]);
47   add(y[i,j],i,j,1);
48  end;
49  readln(q);
50  for i:=1 to q do
51  begin
52   read(j);
53   if j=1 then
54   begin
55    readln(x1,y1,co);
56    add(y[x1,y1],x1,y1,-1);
57    y[x1,y1]:=co;
58    add(co,x1,y1,1);
59   end
60   else
61   begin
62    readln(x1,x2,y1,y2,co);
63    writeln(find(co,x2,y2)-find(co,x1-1,y2)-find(co,x2,y1-1)+find(co,x1-1,y1-1));
64   end;
65  end;
66 end.

View Code

1452: [JSOI2009]Count

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1414 Solved: 831
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

1
2

HINT

Source

JSOI2009Day1

[Submit][Status][Discuss]