1452: [JSOI2009]Count - BZOJ

浏览数：33 / 时间：2015年06月09日

Description

Input

Output

Sample Input

Sample Output

2
HINT

一开始还想什么离线做，其实不用，空间足够，我们直接开100个二维树状数组，然后就行了

但是如果c范围很大就离线做好一些

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