BZOJ1452: [JSOI2009]Count

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

1452: [JSOI2009]Count

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1062 Solved: 625
[Submit][Status]

Description

Input

Output

Sample Input

Sample Output

1
2

HINT

Source

JSOI2009Day1

题解：

暴力维护100棵树状数组。。。

为什么 inc(i,i and (-i))就TLE，写成 i:=i+i and (-i)就尼玛A了。。。

代码：

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