1 //OJ 1610 2 //by Cydiater 3 //2016.9.1 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <iomanip> 9 #include <string>10 #include <queue>11 #include <map>12 #include <algorithm>13 #include <cmath>14 #include <ctime>15 using namespace std;16 #define ll long long17 #define up(i,j,n)       for(int i=j;i<=n;i++)18 #define down(i,j,n)     for(int i=j;i>=n;i--)19 const int MAXN=1e6+5;20 const int oo=0x3f3f3f3f;21 inline int read(){22     char ch=getchar();int x=0,f=1;23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25     return x*f;26 }27 int N,num,root=0,tol=0,maxx,minn,delta;28 ll ans;29 struct node{30     int leftt,rightt,rnd,v;31 }t[MAXN];32 namespace solution{33     void lefturn(int &k){34         int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k;k=tt;35     }36     void righturn(int &k){37         int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k;k=tt;38     }39     void insert(int &k,int x){40         if(k==0){41             k=++tol;42             t[k].leftt=t[k].rightt=0;43             t[k].v=x;t[k].rnd=rand();44             return;45         }46         if(x==t[k].v)return;47         else if(x>t[k].v){48             insert(t[k].rightt,x);49             if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k);50         }51         else if(x<t[k].v){52             insert(t[k].leftt,x);53             if(t[t[k].leftt].rnd<t[k].rnd)righturn(k);54         }55     }56     void query_delta(int k,int x){57         if(k==0)        return;58         if(x<=t[k].v)maxx=min(maxx,t[k].v);59         if(x>=t[k].v)minn=max(minn,t[k].v);60         if(x>t[k].v)query_delta(t[k].rightt,x);61         else        query_delta(t[k].leftt,x);62     }63     void slove(){64         N=read();65         up(i,1,N){66             num=read();67             maxx=oo;minn=-oo;delta=oo;68             query_delta(root,num);69             if(maxx!=-oo)delta=min(delta,abs(maxx-num));70             if(minn!=oo)delta=min(delta,abs(num-minn));71             if(delta>=100000001)delta=num;72             ans+=delta;73             //cout<<num<<‘ ‘<<delta<<‘ ‘<<ans<<endl;74             insert(root,num);75         }76     }77     void output(){78         cout<<ans<<endl;79     }80 }81 int main(){82     //freopen("input.in","r",stdin);83     //freopen("output.out","w",stdout);84     using namespace solution;85     slove();86     output();87     return 0;88 }

  1 //bzoj 1588  2 //by Cydiater  3 //2016.9.6  4 #include <iostream>  5 #include <cstdio>  6 #include <cstdlib>  7 #include <cstring>  8 #include <string>  9 #include <algorithm> 10 #include <queue> 11 #include <map> 12 #include <ctime> 13 #include <cmath> 14 #include <iomanip> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22     char ch=getchar();int x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 map<int,int>lable; 28 struct SplayTree{ 29     int son[2],v,siz,cnt,fa; 30 }t[MAXN]; 31 int N,root=0,tol=0,anss=0; 32 namespace solution{ 33     int get(int x){return t[t[x].fa].son[1]==x;} 34     void clear(int x){t[x].son[0]=t[x].son[1]=t[x].siz=t[x].cnt=t[x].fa=t[x].v=0;} 35     void updata(int x){ 36         if(x){ 37             t[x].siz=t[x].cnt; 38             if(t[x].son[0])t[x].siz+=t[t[x].son[0]].siz; 39             if(t[x].son[1])t[x].siz+=t[t[x].son[1]].siz; 40         } 41     } 42     inline void rotate(int x){//rotate now node to root 43         int old=t[x].fa,oldf=t[old].fa,which=get(x); 44         t[old].son[which]=t[x].son[which^1];t[t[old].son[which]].fa=old; 45         t[old].fa=x;t[x].son[which^1]=old; 46         t[x].fa=oldf; 47         if(oldf)t[oldf].son[t[oldf].son[1]==old]=x; 48         updata(old);updata(x); 49     } 50     void splay(int x){ 51         for(int fa;(fa=t[x].fa);rotate(x))if(t[fa].fa) 52         rotate(get(x)==get(fa)?fa:x);root=x; 53     } 54     inline void insert(int v){ 55         if(root==0){ 56             root=++tol; 57             t[root].son[0]=t[root].son[1]=t[root].fa=0; 58             t[root].v=v;t[root].cnt=t[root].siz=1; 59             return; 60         } 61         int now=root,fa=0; 62         while(1){ 63             if(t[now].v==v){ 64                 t[now].cnt++;updata(now);updata(fa); 65                 splay(now);break; 66             } 67             fa=now;now=t[now].son[t[now].v<v]; 68             if(now==0){ 69                 now=++tol; 70                 t[now].son[0]=t[now].son[1]=0;t[now].v=v; 71                 t[now].siz=t[now].cnt=1;t[now].fa=fa; 72                 t[fa].son[t[fa].v<v]=tol; 73                 updata(fa); 74                 splay(now); 75                 break; 76             } 77         } 78     } 79     int find(int x){ 80         int now=root,ans=0; 81         while(1){ 82             if(x<t[now].v)now=t[now].son[0]; 83             else{ 84                 ans+=(t[now].son[0]?t[t[now].son[0]].siz:0); 85                 if(t[now].v==x){ 86                     splay(now); 87                     return ans+1; 88                 } 89                 ans+=t[now].cnt; 90                 now=t[now].son[1]; 91             } 92         } 93     } 94     int pre(){ 95         int now=t[root].son[0]; 96         while(t[now].son[1])now=t[now].son[1]; 97         return now; 98     } 99     int nxt(){100         int now=t[root].son[1];101         while(t[now].son[0])now=t[now].son[0];102         return now;103     }104     void del(int x){105         int whatever=find(x);106         if(t[root].cnt>1){107             t[root].cnt--;108             t[root].siz--;109         }110         if(t[root].son[1]+t[root].son[0]==0){111             clear(root);root=0;112             return;113         }114         if(!t[root].son[0]){115             int oldroot=root;root=t[root].son[1];t[root].fa=0;116             clear(oldroot);return;117         }else if(!t[root].son[1]){118             int oldroot=root;root=t[root].son[0];t[root].fa=0;119             clear(oldroot);return;120         }121         int leftbig=pre(),oldroot=root;splay(leftbig);122         t[t[oldroot].son[1]].fa=root;t[root].son[1]=t[oldroot].son[1];123         clear(root);updata(root);124     }125     void debug(int now){126         printf("now=%d t[now].son[0]=%d t[now].son[1]=%d t[now].siz=%d t[now].cnt=%d t[now].fa=%d t[now].v=%d\n",now,t[now].son[0],t[now].son[1],t[now].siz,t[now].cnt,t[now].fa,t[now].v);127         if(t[now].son[0])debug(t[now].son[0]);128         if(t[now].son[1])debug(t[now].son[1]);129     }130 }131 int main(){132     //freopen("input.in","r",stdin);133     //freopen("output.out","w",stdout);134     using namespace solution;135     N=read();136     while(N--){137         int num=read();if(lable[num])continue;138         insert(num);lable[num]=1;139         int maxx=nxt(),minn=pre();140         int tmp=oo;141         if(maxx==minn&&minn==0)tmp=num;142         if(maxx)tmp=min(tmp,t[maxx].v-num);143         if(minn)tmp=min(tmp,num-t[minn].v);144         anss+=tmp;145         //debug(root);puts("");146     }147     printf("%d\n",anss);148     return 0;149 }