[SBT模板题]HNOI2002 营业额统计

http://www.lydsy.com/JudgeOnline/problem.php?id=1588

1588: [HNOI2002]营业额统计

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 2884 Solved: 901
[Submit][Status][Discuss]

Description

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：该天的最小波动值当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。

Input

第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数，表示第i天公司的营业额。

Output

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

Sample Input

6
5
1
2
5
4
6

Sample Output

HINT

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

/**************************************************************
    Problem: 1588
    User: HTwood
    Language: Pascal
    Result: Accepted
    Time:428 ms
    Memory:2816 kb
****************************************************************/
 
program SBT;
 
Const
 OLeft=false;
 ORight=true;
 
Type
 node=^rec;
 rec=record
   k,s:longint;
   lch,rch:node;
 end;
  
Var
 h,null:node;
 n,i,p,ans:longint;
  
Procedure maintain(var p:node;flag:boolean);forward;
 
Procedure init(var p:node;num:longint);
  begin
  p^.lch:=null;
  p^.rch:=null;
  p^.s:=1;
  p^.k:=num;
end;
 
Procedure add(var p:node;num:longint);
  begin
  if p=null then
    begin
    new(p);
    init(p,num);
    exit;
  end;
  if num<=p^.k then add(p^.lch,num) else add(p^.rch,num);
  inc(p^.s);
  maintain(p,num>p^.k);
end;
 
Procedure leftR(var p:node);//将P推向左下方，返回新树的父亲
var
 newroot:node;
  begin
  new(newroot);
  newroot:=p^.rch;
  p^.rch:=newroot^.lch;
  newroot^.lch:=p;
    p^.s:=p^.lch^.s+p^.rch^.s+1;
    newroot^.s:=newroot^.lch^.s+newroot^.rch^.s+1;
    p:=newroot;
end;
 
Procedure RightR(var p:node);//将P推向右下方，返回新树的父亲
var
 newroot:node;
  begin
  new(newroot);
  newroot:=p^.lch;
  p^.lch:=newroot^.rch;
  newroot^.rch:=p;
    p^.s:=p^.lch^.s+p^.rch^.s+1;
    newroot^.s:=newroot^.lch^.s+newroot^.rch^.s+1;
    p:=newroot;
end;
   
Procedure view(P:node);
  begin
  if p=null then exit;
  writeln('P^.s=',p^.s,' p^.k=',p^.k);
  view(p^.lch);
  view(p^.rch);
end;
 
Procedure maintain(var p:node;flag:boolean);
  begin
  if p=null then exit;
  if flag=Oleft then
    if p^.lch^.lch^.s>p^.rch^.s then
      RightR(P)
    else
    if p^.lch^.rch^.s>p^.rch^.s then
      begin
      leftR(p^.lch);
      rightr(p);
    end
    else
    exit
  else
    if p^.rch^.rch^.s>p^.lch^.s then
      LeftR(p)
    else
    if p^.rch^.lch^.s>p^.lch^.s then
      begin
      rightr(p^.rch);
      leftr(p);
    end
    else
    exit;
  maintain(p^.lch,Oleft);
  maintain(p^.rch,ORight);
  maintain(p,Oleft);
  maintain(p,Oright);
end;
         
Function Select(var p:node;o:longint):node;
var
 mid:longint;
  begin
    if p=null then exit(null);
    mid:=p^.lch^.s+1;
    if o=mid then exit(p);
    if o<mid then exit(select(p^.lch,o));
    if o>mid then exit(select(p^.rch,o-mid));
end;
 
function find(var p:node;o:longint):longint;
  begin
    if p^.k=o then exit(o);
    if o<p^.k then
      if p^.lch=null then find:=p^.k else find:=find(p^.lch,o)
    else
      if p^.rch=null then find:=p^.k else find:=find(p^.rch,o);
    if abs(find-o)>abs(p^.k-o) then find:=p^.k;
end;
     
  begin
  readln(n);
     
    new(null);
    with null^ do
      begin
        s:=0;
        k:=0;
        lch:=null;
        rch:=null;
    end;
     
    h:=null;
    ans:=0;
  for i:=1 to n do
    begin
        if eof then p:=0 else
    readln(p);
        inc(ans,abs(find(h,p)-p));
    add(h,p);
  end;
  writeln(ans);
end.