9
2
2013
0

【BZOJ1452】【JSOI2009】Count【二维树状数组】

大水题一只,开100个二维树状数组表示,每一种颜色就可以了,查询的复杂度只有logm*logn,非常快。由于最近手残的严重,我还是喜闻乐见的WA了一次。

program p1452;
	var
		x:array[1..305,1..305,1..105] of longint;
		f:array[1..305,1..305] of longint;
		i,j,n,m,q,k1,k2,k3,k4,k5,k6:longint;
	function lowbit(k:longint):longint;
		begin
			exit(k and (-k));
		end;
	procedure add(k1,k2,k3,k4:longint);
		var
			i,j:longint;
		begin
			i:=k1;
			while i<=n do begin
				j:=k2;
				while j<=m do begin
					inc(x[i,j,k3],k4);
					j:=j+lowbit(j);
				end;
				i:=i+lowbit(i);
			end;
		end;
	function find(k1,k2,k3:longint):longint;
		var
			i,j,num:longint;
		begin
			i:=k1; num:=0;
			while i>0 do begin
				j:=k2;
				while j>0 do begin
					inc(num,x[i,j,k3]);
					j:=j-lowbit(j);
				end;
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	begin
		readln(n,m);
		fillchar(x,sizeof(x),0);
		for i:=1 to n do
			for j:=1 to m do begin
				read(f[i,j]);
				add(i,j,f[i,j],1);
			end;
		read(q);
		for i:=1 to q do begin
			read(k1);
			if k1=1 then begin
				readln(k2,k3,k4);
				add(k2,k3,f[k2,k3],-1);
				add(k2,k3,k4,1);
				f[k2,k3]:=k4;
			end else begin
				readln(k2,k4,k3,k5,k6);
				writeln(find(k4,k5,k6)+find(k2-1,k3-1,k6)-find(k2-1,k5,k6)-find(k4,k3-1,k6));
			end;
		end;
	end.
Category: 数据结构 | Tags: | Read Count: 800

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com