记录编号	423688	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.116 s
提交时间	2017-07-12 13:07:34	内存使用	1.46 MiB

#include<stdio.h>
#include<iostream>
#include<ctime>
#include<cmath>
#include<cstdlib>
#define maxn 50005
#define inf 10000000
using namespace std;
int zz,n,so,tot,root;
int fro,bac;
struct tree{
       int l,r,no;
       int size,tot,rd;
       }t[maxn];
void l_swap(int &now){
     int newnow=t[now].r;
     t[now].r=t[newnow].l;
     t[newnow].l=now;
     t[newnow].size=t[now].size;
     t[now].size=t[t[now].l].size+t[t[now].r].size+t[now].tot;
     now=newnow;
}
void r_swap(int &now){
     int newnow=t[now].l;
     t[now].l=t[newnow].r;
     t[newnow].r=now;
     t[newnow].size=t[now].size;
     t[now].size=t[t[now].l].size+t[t[now].r].size+t[now].tot;
     now=newnow;
}
void buildtree(int &root,int no){
     if(root==0){
        root=++zz;
        t[root].size=t[root].tot=1;
        t[root].no=no;
        t[root].rd=rand();
     } 
     t[root].size++;
     if(t[root].no==no) t[root].tot++;
     else{
          if(t[root].no>no){
             buildtree(t[root].l,no);
             if(t[t[root].l].rd<t[root].rd)
               r_swap(root);
          }
          else{
             buildtree(t[root].r,no);
             if(t[t[root].r].rd<t[root].rd)
               l_swap(root);
          }
     }
}
void find_anc(int &root,int x){
     if(root==0) return;
     if(t[root].no==x){
        fro=t[root].no;
        return;
     }
     if(t[root].no<x){
       fro=t[root].no;
       find_anc(t[root].r,x);
     }
     else find_anc(t[root].l,x);
}
void find_bac(int &root,int x){
     if(root==0) return;
     if(t[root].no==x){
        bac=t[root].no;
        return;
     }
     if(t[root].no>x){
       bac=t[root].no;
       find_bac(t[root].l,x);
     }
     else find_bac(t[root].r,x);
}
int main(){
    freopen("turnover.in","r",stdin);
    freopen("turnover.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&so);
        if(i==1) tot+=so;
        else{  
           fro=-inf; bac=-inf;
           find_anc(root,so);
           find_bac(root,so);
           int newso=min(abs(fro-so),abs(bac-so));
           tot+=newso;
        }
        buildtree(root,so);
        //cout<<tot<<" ";
    }
    printf("\n%d",tot);
    //system("pause");
    return 0;
}