1. 题目

BZOJ 传送门=￣ω￣=
LUOGU 传送门=￣ω￣=

2. 题解

之前发了个 treap 版的
现在发个 splay 版的

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();bool flag=0;dig=0;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')flag=1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
LL n,root,cnt,ans;
struct N{LL s[2],f,d;N(){f=d=s[0]=s[1]=0;}}e[40000];
bool pos(LL a){return e[e[a].f].s[1]==a;}
void rot(LL a)
{
    LL f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
}
void splay(LL a)
{
    while(e[a].f)
        if(!e[e[a].f].f)rot(a);
        else
            if(pos(a)^pos(e[a].f))rot(a),rot(a);
            else rot(e[a].f),rot(a);
    root=a;
}
void insert(LL k,LL fa,LL&a)
{
    if(!a){a=++cnt,e[a].d=k,e[a].f=fa,splay(a);return;}
    if(k<e[a].d)insert(k,a,e[a].s[0]);
    else if(k>e[a].d)insert(k,a,e[a].s[1]);
}
LL nxt(LL k,LL a)
{
    if(!a)return 1e8;
    if(e[a].d==k){splay(a);return k;}
    if(e[a].d>k)return min(nxt(k,e[a].s[0]),e[a].d);
    return nxt(k,e[a].s[1]);
}
LL pre(LL k,LL a)
{
    if(!a)return -1e8;
    if(e[a].d==k){splay(a);return k;}
    if(e[a].d<k)return max(pre(k,e[a].s[1]),e[a].d);
    return pre(k,e[a].s[0]);
}
int main()
{
    IN(n),IN(ans),insert(ans,0,root);
    for(LL i=2,a;i<=n;i++)
        IN(a),ans+=min(a-pre(a,root),nxt(a,root)-a),insert(a,0,root);
    printf("%lld\n",ans);
    return 0;
}