记录编号	175896	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.409 s
提交时间	2015-08-07 14:17:00	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
struct node{
    node *left,*right;
    int v,p,cnt,sz;
}*root,*null=new node((node){null,null,0,0,0,0});
int ans=0,n;
map<int,int>mp;

void push_up(node *x){
    x->sz=x->left->sz+x->right->sz+x->cnt;
}

void lturn(node *&x){
    node *y=x->right;
    x->right=y->left; y->left=x;
    y->sz=x->sz; push_up(x); x=y;
}

void rturn(node *&x){
    node *y=x->left;
    x->left=y->right; y->right=x;
    y->sz=x->sz; push_up(x); x=y;
}

void Insert(node *&x,int k){
    if (!x->sz){
        x=new node;
        x->left=x->right=null;
        x->v=k; x->p=rand();
        x->sz=x->cnt=1;
        return;
    }
    x->sz++;
    if (k==x->v) x->cnt++;
    else if (k>x->v){
        Insert(x->right,k);
        if (x->right->p<x->p) lturn(x);
    }
    else {
        Insert(x->left,k);
        if (x->left->p<x->p) rturn(x);
    }
}
int Q_rank(node *x,int k){
    if (!x->sz) return 0;
    if (k==x->v) return x->left->sz+1;
    else if (k<x->v) return Q_rank(x->left,k);
    else return Q_rank(x->right,k)+x->left->sz+x->cnt;
}

int Q_num(node *x,int k){
    if (!x->sz) return 0;
    if (k<=x->left->sz) return Q_num(x->left,k);
    else if (k>x->left->sz+x->cnt)
        return Q_num(x->right,k-x->left->sz-x->cnt);
    else return x->v;
}

int Q_pro(node *x,int k,int c){
    if (!x->sz) return c;
    if (k>x->v) return Q_pro(x->right,k,x->v);
    else return Q_pro(x->left,k,c);
}

int Q_suc(node *x,int k,int c){
    if (!x->sz) return c;
    if (k<x->v) return Q_suc(x->left,k,x->v);
    else return Q_suc(x->right,k,c);
}

int main()
{
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
	scanf("%d",&n); root=null; int num1,num2;
	for (int i=1;i<=n;++i){
		int x; num1=num2=0x7fffffff/2;
		if(scanf("%d",&x)==EOF)x=0;
		Insert(root,x);
		if (i==1) {ans+=x; mp[x]=1;}
		else {
			if (mp[x]) continue;
			int k=Q_rank(root,x);
			if (k>1) num1=Q_num(root,k-1);
			if (k<i) num2=Q_num(root,k+1);
			ans+=min(abs(num1-x),abs(num2-x));
			mp[x]=1;
		}
		
	}
	printf("%d",ans); //system("pause");
	return 0;
}