记录编号	423749	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.115 s
提交时间	2017-07-12 15:26:28	内存使用	11.76 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 500010
struct Treap
{
       int l,r,w,v,size,rnd;
       Treap(){v=-1000000;}
}tree[N];
int n;
int root,size;
void update(int k)
{
     tree[k].size=tree[tree[k].l].size+tree[tree[k].r].size+tree[k].w;
}
void rturn(int &k)
{
     int t=tree[k].l;
     tree[k].l=tree[t].r;
     tree[t].r=k;
     tree[t].size=tree[k].size;
     update(k);
     k=t;
}
void lturn(int &k)
{
     int t=tree[k].r;
     tree[k].r=tree[t].l;
     tree[t].l=k;
     tree[t].size=tree[k].size;
     update(k);
     k=t;
}
void insert(int &k,int x)
{
    if(k==0)
    {
       size++;
       k=size;
       tree[k].w=tree[k].size=1;
       tree[k].v=x;
       tree[k].rnd=rand();
       return;
    }
    tree[k].size++;
    if(tree[k].v==x)
       tree[k].w++;
    else
    {
        if(tree[k].v<x)
        {
           insert(tree[k].r,x);
           if(tree[tree[k].r].rnd<tree[k].rnd)
              lturn(k);
        }
        else
        {
            insert(tree[k].l,x);
            if(tree[tree[k].l].rnd<tree[k].rnd)
              rturn(k);
        }
    }
}
int ans;
int abs(int x)
{
    if(x<0)
      return -x;
    return x;
}
int tmp1,tmp2;
void query_pro(int k,int x)
{
    if(k==0)
      return;
    if(tree[k].v==x)
    {
       tmp1=k;
       return;
    }
    if(x>tree[k].v)
    {
       tmp1=k;
       query_pro(tree[k].r,x);
    }
    else
      query_pro(tree[k].l,x);
}
void query_sub(int k,int x)
{
     if(k==0)
      return;
     if(tree[k].v==x)
     {
       tmp2=k;
       return;
     }
     if(x<tree[k].v)
     {
       tmp2=k;
       query_sub(tree[k].l,x);
     }
     else
      query_sub(tree[k].r,x);
}
int main()
{
    freopen("turnover.in","r",stdin);
    freopen("turnover.out","w",stdout);
    scanf("%d",&n);
    pos(i,1,n)
    {
       int x;
       scanf("%d",&x);
       
       if(i==1)
         ans+=x;
       
       else
       {
          tmp1=tmp2=0;query_pro(root,x);query_sub(root,x);
          //cout<<"i="<<i<<"   pro="<<tree[tmp1].v<<"   sub="<<tree[tmp2].v<<endl;
          ans+=min(abs(tree[tmp1].v-x),abs(tree[tmp2].v-x));
          
          
       }
       //cout<<"ans="<<ans<<endl;
       insert(root,x);
    }
    printf("%d",ans);
    //while(1);
    return 0;
}