平衡树裸题
只需要求前驱后驱
treap写法
const
mm=<<;
maxnumber=;
maxn=; var
left,right,fix,key:array[..maxn]of longint;
t,n,ans,i,j,k,l,tot:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; function max(x,y:longint):longint;
begin
if x<y then exit(y);
exit(x);
end; procedure lt(var t:longint);
var
k:longint;
begin
k:=right[t];
right[t]:=left[k];
left[k]:=t;
t:=k;
end; procedure rt(var t:longint);
var
k:longint;
begin
k:=left[t];
left[t]:=right[k];
right[k]:=t;
t:=k;
end; procedure insert(var t:longint;v:longint);
begin
if t= then begin
inc(tot);
t:=tot;
key[t]:=v;
fix[t]:=random(maxnumber)+;
left[t]:=;
right[t]:=;
exit;
end;
if v<=key[t] then begin
insert(left[t],v);
if fix[left[t]]>fix[t] then rt(t);
end
else begin
insert(right[t],v);
if fix[right[t]]>fix[t] then lt(t);
end;
end; function pred(t,v:longint):longint;
begin
if t= then exit(-mm);
if v=key[t] then exit(v);
if v<key[t] then exit(pred(left[t],v))
else
exit(max(key[t],pred(right[t],v)));
end; function succ(t,v:longint):longint;
begin
if t= then exit(mm);
if v=key[t] then exit(v);
if v<key[t] then exit(min(key[t],succ(left[t],v)))
else
exit(succ(right[t],v));
end; begin
t:=;
readln(n);
read(j);
insert(t,j);
ans:=j;
for i:= to n do begin
read(j);
k:=pred(t,j);
l:=succ(t,j);
// writeln(j,' ',k,' ',l);
if j-k<l-j then ans:=ans+j-k
else ans:=ans+l-j;
insert(t,j);
end;
writeln(ans);
readln;
readln;
end.