实现功能——对于一个N×M的方格,1:输入一个区域,将此区域全部值作加法;2:输入一个区域,求此区域全部值的和
其实和一维线段树同理,只是不知道为什么速度比想象的慢那么多,求解释。。。@acphile
(还有代码略恶心,求原谅。。。^_^)
const tvp=;
var
i,j,k,l,m,n,a1,a2,a3,a4,a5:longint;
a,b:array[..tvp] of longint;
c1,c2:char;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
function op(z,x1,y1,x2,y2,lx,ly,rx,ry,nu,d:longint):longint;inline;
var
a1,a2,a3,a4,a5:longint;
begin
if (lx>rx) or (ly>ry) then exit();
if (x1=lx) and (y1=ly) and (x2=rx) and (y2=ry) then
begin
b[z]:=b[z]+nu;
exit(nu*(rx-lx+)*(ry-ly+));
end;
a2:=op(z*-,x1,y1,(x1+x2) div ,(y1+y2) div ,lx,ly,min(rx,(x1+x2) div ),min(ry,(y1+y2) div ),nu,d);
a3:=op(z*-,x1,(y1+y2) div +,(x1+x2) div ,y2,lx,max(ly,(y1+y2) div +),min(rx,(x1+x2) div ),ry,nu,d);
a4:=op(z*,(x1+x2) div +,y1,x2,(y1+y2) div ,max(lx,(x1+x2) div +),ly,rx,min(ry,(y1+y2) div ),nu,d);
a5:=op(z*+,(x1+x2) div +,(y1+y2) div +,x2,y2,max(lx,(x1+x2) div +),max(ly,(y1+y2) div +),rx,ry,nu,d);
a[z]:=a[z]+a2+a3+a4+a5;
exit(a2+a3+a4+a5);
end;
function cal(z,x1,y1,x2,y2,lx,ly,rx,ry,d:longint):longint;inline;
var a1,a2,a3,a4,a5:longint;
begin
if (lx>rx) or (ly>ry) then exit();
d:=d+b[z];
if (x1=lx) and (y1=ly) and (x2=rx) and (y2=ry) then exit(a[z]+d*(rx-lx+)*(ry-ly+));
a2:=cal(z*-,x1,y1,(x1+x2) div ,(y1+y2) div ,lx,ly,min(rx,(x1+x2) div ),min(ry,(y1+y2) div ),d);
a3:=cal(z*-,x1,(y1+y2) div +,(x1+x2) div ,y2,lx,max(ly,(y1+y2) div +),min(rx,(x1+x2) div ),ry,d);
a4:=cal(z*,(x1+x2) div +,y1,x2,(y1+y2) div ,max(lx,(x1+x2) div +),ly,rx,min(ry,(y1+y2) div ),d);
a5:=cal(z*+,(x1+x2) div +,(y1+y2) div +,x2,y2,max(lx,(x1+x2) div +),max(ly,(y1+y2) div +),rx,ry,d);
exit(a2+a3+a4+a5);
end;
begin
readln(c1,n,m);
fillchar(a,sizeof(a),);
fillchar(b,sizeof(b),);
while not(eof) do
begin
read(c1,a1,a2,a3,a4);
case c1 of
'L':begin
readln(a5);
op(,,,n,m,a1,a2,a3,a4,a5,);
end;
'k':begin
readln;
writeln(cal(,,,n,m,a1,a2,a3,a4,));
end;
end;
end;
end.