首页 > 代码库 > BZOJ1452: [JSOI2009]Count
BZOJ1452: [JSOI2009]Count
1452: [JSOI2009]Count
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1062 Solved: 625
[Submit][Status]
Description
Input
Output
Sample Input
Sample Output
1
2
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 do10 begin11 i:=y;12 while i<=m do13 begin14 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 begin23 sum:=0;24 while x>0 do25 begin26 i:=y;27 while i>0 do28 begin29 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 begin38 readln(n,m);39 for i:=1 to n do40 begin41 for j:=1 to m do42 begin43 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 begin51 readln(q);52 for i:=1 to q do53 begin54 read(ch);55 case ch of56 1:begin57 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:begin63 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 begin70 assign(input,‘input.txt‘);assign(output,‘ouput.txt‘);71 reset(input);rewrite(output);72 init;73 main;74 close(input);close(output);75 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。