Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 注意事项以及一些想法。

Posted by The_Dawn at 2011-07-14 16:26:03 on Problem 3277
```1、不止ans，tree的左右区间也要开到int64,数据坑爹。
2、因为40000条线，所以是80000的点，所以树应该开到400000左右。

discuss里有一些关于什么区间半开半闭什么的东西，我AC了以后也没弄懂是什么意思。本人理解能力不够的缘故吧。

type
node=record
l,r,h,cover:int64;
end;

var
n,i,j,k,st,ed,h:longint;
ans:int64;
high,verl,verr:array[0..40001]of longint;
axis:array[0..90000]of longint;
tree:array[0..400000]of node;

procedure init;
begin
for i:=1 to n do
begin
axis[i]:=verl[i];
axis[i+n]:=verr[i];
end;
end;

procedure sort(l,r:longint);
var
i,j,x,y:longint;
begin
i:=l;j:=r;
x:=high[(l+r)shr 1];
repeat
while high[i]<x do inc(i);
while high[j]>x do dec(j);
if not (i>j) then
begin
y:=high[i];high[i]:=high[j];high[j]:=y;
y:=verl[i];verl[i]:=verl[j];verl[j]:=y;
y:=verr[i];verr[i]:=verr[j];verr[j]:=y;
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

procedure sortaxis(l,r:longint);
var
i,j,x,y:longint;
begin
i:=l;j:=r;
x:=axis[(l+r)shr 1];
repeat
while axis[i]<x do inc(i);
while axis[j]>x do dec(j);
if not (i>j) then
begin
y:=axis[i];axis[i]:=axis[j];axis[j]:=y;
inc(i);dec(j);
end;
until i>j;
if l<j then sortaxis(l,j);
if i<r then sortaxis(i,r);
end;

function map(x:longint):longint;
var
mid,l,r:longint;
begin
l:=1;r:=2*n;
while l<=r do
begin
mid:=(l+r)shr 1;
if axis[mid]=x then exit(mid);
if x>axis[mid] then l:=mid+1 else r:=mid;
end;
end;

procedure build(w,l,r:longint);
var
mid:longint;
begin
tree[w].l:=l;tree[w].r:=r;
if l>=r then exit;
mid:=(l+r)shr 1;
build(2*w,l,mid);
build(2*w+1,mid+1,r);

end;

begin
tree[w].cover:=0;
tree[2*w].h:=tree[w].h;
tree[2*w+1].h:=tree[w].h;
tree[2*w].cover:=1;
tree[2*w+1].cover:=1;
end;

procedure change(w:longint);
var
mid:longint;
begin
if (st<=tree[w].l)and(tree[w].r<=ed) then
begin
tree[w].h:=high[i];
tree[w].cover:=1;
exit;
end;
mid:=(tree[w].l+tree[w].r)shr 1;
if st<=mid then change(2*w);
if mid<ed then change(2*w+1);
end;

procedure sum(w:longint);
begin
if (tree[w].l=0)or(tree[w].l>tree[w].r) then exit;
if tree[w].cover=1 then
begin
ans:=ans+(axis[tree[w].r+1]-axis[tree[w].l])*tree[w].h;
exit;
end;
sum(2*w);
sum(2*w+1);
end;

begin
//assign(input,'1.txt');
//assign(output,'2.txt');
//reset(input);rewrite(output);

init;
sort(1,n);
sortaxis(1,2*n);
build(1,1,2*n);
for i:=1 to n do
begin
st:=map(verl[i]);
ed:=map(verr[i])-1;
change(1);
end;
sum(1);
writeln(ans);

//close(input);close(output);
end.
```

Followed by: