#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; #define inf 1000000000 inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=50001; int n,ans,sz,rt,t1,t2,c[maxn][2],fa[maxn],num[maxn]; inline void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else{ if(c[z][0]==y)c[z][0]=x; else c[z][1]=x; } fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; } inline void splay(int x,int &k){ int y,z; while(x!=k){ y=fa[x];z=fa[y]; if(y!=k){ if((c[y][0]==x)^(c[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } inline void ins(int &k,int x,int last){ if(!k){num[k=++sz]=x;fa[k]=last;splay(k,rt);return;} if(x<num[k])ins(c[k][0],x,k); else ins(c[k][1],x,k); } inline void ask_prev(int k,int x) { if(!k)return; if(num[k]<=x){t1=num[k];ask_prev(c[k][1],x);} else ask_prev(c[k][0],x); } inline void ask_succ(int k,int x){ if(!k)return; if(num[k]>=x){t2=num[k];ask_succ(c[k][0],x);} else ask_succ(c[k][1],x); } int main(){ n=read(); for(int i=1;i<=n;i++){ int x;if(scanf("%d",&x)==EOF)x=0; t1=-inf;t2=inf; ask_prev(rt,x);ask_succ(rt,x); if(i!=1)ans+=min(x-t1,t2-x); else ans+=x; ins(rt,x,0); } printf("%d",ans); return 0; }
4.20 * 1 (Treap)
#include<iostream> #include<cstdlib> #include<cstdio> #include<ctime> #define inf 1000000000 using namespace std; struct data{ int l,r,num,rnd; }tr[50001]; int n,size,root,ans1,ans2,ans; void lturn(int &k){ int t=tr[k].r; tr[k].r=tr[t].l; tr[t].l=k; k=t; } void rturn(int &k){ int t=tr[k].l; tr[k].l=tr[t].r; tr[t].r=k; k=t; } void insert(int &k,int x){ if(k==0){ k=++size; tr[k].num=x; tr[k].rnd=rand(); return; } if(x<tr[k].num){ insert(tr[k].l,x); if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k); } else if(x>tr[k].num){ insert(tr[k].r,x); if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k); } } void ask_before(int k,int x){ if(k==0)return; else if(x>=tr[k].num){ans1=tr[k].num;ask_before(tr[k].r,x);} else ask_before(tr[k].l,x); } void ask_after(int k,int x){ if(k==0)return; else if(x<=tr[k].num){ans2=tr[k].num;ask_after(tr[k].l,x);} else ask_after(tr[k].r,x); } int main(){ scanf("%d",&n);int t; for(int i=1;i<=n;i++){ if(scanf("%d",&t)==EOF)t=0; ans1=-inf;ans2=inf; ask_before(root,t); ask_after(root,t); if(i!=1)ans+=min(t-ans1,ans2-t); else ans+=t; insert(root,t); } printf("%d",ans); return 0; }
7.28 * 1 (Splay)