Luogu

算法

对数据排序后，与某个数的差得绝对值最小的一定是它的前面或后面那个数。

考虑用平衡树维护这个过程。我们只要支持插入、求前驱、求后继这三个操作即可。

注意这里的前驱后继不要求严格。我用的是$\color{red}{fhq\ treap}$，所以把前驱的$k-1$改成$k$，后继的$k$改成$k-1$即可。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MAXN=32767+10;
const int INF=100000010;

struct Treap {
    int ch[MAXN][2];
    int val[MAXN];
    int rnd[MAXN];
    int sz[MAXN];
    int cnt,root,x,y;
    
    inline int new_node(int x) { val[++cnt]=x,rnd[cnt]=rand(),sz[cnt]=1; return cnt; }
    inline void pushup(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; }
    
    inline void split(int now,int k,int& x,int& y) {
        if (!now) { x=y=0; return; }
        if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
        else y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
    
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); pushup(A); return A; }
        else { ch[B][0]=merge(A,ch[B][0]); pushup(B); return B; }
    }
    
    inline int kth(int now,int k) {
        while (1) {
            if (k<=sz[ch[now][0]]) now=ch[now][0];
            else if (k==sz[ch[now][0]]+1) return now;
            else k-=sz[ch[now][0]]+1,now=ch[now][1];
        }
    }
    
    inline int GetLower(int k) {
        split(root,k,x,y);
        int ans=val[kth(x,sz[x])];
        root=merge(x,y);
        return ans;
    }
    
    inline int GetUpper(int k) {
        split(root,k-1,x,y);
        int ans=val[kth(y,1)];
        root=merge(x,y);
        return ans;
    }
    
    inline void insert(int k) {
        split(root,k,x,y);
        root=merge(merge(x,new_node(k)),y);
    }
};

Treap T;

mainint main() {
    int n=read(),ans=read(); T.cnt=T.root=T.x=T.y=0;
    T.insert(ans); T.insert(-INF); T.insert(INF);
    for (re int i=2;i<=n;i++) {
        int k=read();
        int a=T.GetLower(k),b=T.GetUpper(k);
        ans+=min(abs(k-a),abs(b-k));
        T.insert(k);
    }
    printf("%lld\n",ans);
    return 0;
}