## poj1389——by rfy

2018年05月02日 算法 ⁄ 共 2424字 ⁄ 字号 评论关闭
```type
tree=record
l,r,v,fl:int64;
end;
bian=record
x,y1,y2,pd:int64;
end;
var
x,y,xx,yy,num,ans,max:int64;
i:longint;
t:array[1..1000000] of tree;
b:array[1..1000000] of bian;

function maxn(a,b:int64):int64;
begin
if a>b then
exit(a)
else exit(b);
end;

procedure sort(l,r: int64);
var
i,j,x,y: int64;
begin
i:=l;
j:=r;
x:=b[(l+r) div 2].x;
repeat
while b[i].x<x do
inc(i);
while x<b[j].x do
dec(j);
if not(i>j) then
begin
y:=b[i].x;
b[i].x:=b[j].x;
b[j].x:=y;
y:=b[i].y1;
b[i].y1:=b[j].y1;
b[j].y1:=y;
y:=b[i].y2;
b[i].y2:=b[j].y2;
b[j].y2:=y;
y:=b[i].pd;
b[i].pd:=b[j].pd;
b[j].pd:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

procedure build(p,x,y:int64);
begin
t[p].l:=x;
t[p].r:=y;
t[p].v:=0;
t[p].fl:=0;
if x<>y then
begin
build(p*2,x,(x+y) div 2);
build(p*2+1,(x+y) div 2+1,y);
end;
end;

procedure wh(p:int64);
begin
if t[p].l=t[p].r then
begin
if t[p].v=0 then
t[p].fl:=0
else t[p].fl:=1;
exit;
end;
if t[p].v>0 then
begin
t[p].fl:=1;
exit;
end;
if (t[p*2].fl=1)and(t[p*2+1].fl=1) then
begin
t[p].fl:=1;
exit;
end;
if (t[p*2].fl=0)and(t[p*2+1].fl=0) then
begin
t[p].fl:=0;
exit;
end;
t[p].fl:=-1;
end;

procedure insert(p,x,y:int64);
var mid:int64;
begin
if x>y then
exit;
if (t[p].l=x)and(t[p].r=y) then
begin
inc(t[p].v);
wh(p);
exit;
end;
mid:=(t[p].l+t[p].r) div 2;
if y<=mid then
begin
insert(p*2,x,y);
wh(p);
exit;
end;
if x>mid then
begin
insert(p*2+1,x,y);
wh(p);
exit;
end;
insert(p*2,x,mid);
insert(p*2+1,mid+1,y);
wh(p);
end;

procedure delete(p,x,y:int64);
var mid:int64;
begin
if x>y then
exit;
if (t[p].l=x)and(t[p].r=y) then
begin
dec(t[p].v);
wh(p);
exit;
end;
mid:=(t[p].l+t[p].r) div 2;
if y<=mid then
begin
delete(p*2,x,y);
wh(p);
exit;
end;
if x>mid then
begin
delete(p*2+1,x,y);
wh(p);
exit;
end;
delete(p*2,x,mid);
delete(p*2+1,mid+1,y);
wh(p);
end;

function sum(p:int64):int64;
var mid:int64;
begin
if t[p].fl=0 then
exit(0);
if t[p].fl=1 then
exit(t[p].r-t[p].l+1);
exit(sum(p*2)+sum(p*2+1));
end;

begin
while true do
begin
num:=0;
max:=0;
if x=-1 then
break;
inc(x);
inc(xx);
inc(y);
inc(yy);
inc(num);
b[num].x:=x;
b[num].y1:=y;
b[num].y2:=yy;
b[num].pd:=0;
inc(num);
b[num].x:=xx;
b[num].y1:=y;
b[num].y2:=yy;
b[num].pd:=1;
if yy>max then
max:=yy;
while true do
begin
if x=-1 then
break;
inc(x);
inc(xx);
inc(y);
inc(yy);
if yy>max then
max:=yy;
inc(num);
b[num].x:=x;
b[num].y1:=y;
b[num].y2:=yy;
b[num].pd:=0;
inc(num);
b[num].x:=xx;
b[num].y1:=y;
b[num].y2:=yy;
b[num].pd:=1;
end;
sort(1,num);
max:=max*2;
build(1,1,max);
ans:=0;
for i:=1 to num do
begin
if i<>1 then
ans:=ans+maxn((sum(1)),0)*(b[i].x-b[i-1].x);
if b[i].pd=0 then
insert(1,b[i].y1+1,b[i].y2)
else delete(1,b[i].y1+1,b[i].y2);
end;
writeln(ans);
end;
end.```