题目分析:
题目要求我们能够快速地找到序列中某数的前驱以及后继,那么我们如何实现呢。
首先,我们显然可以使用平衡树去完成此题,毕竟这是平衡树的看家本领,那么复杂度为O(nlogn)的平衡树效果如何呢?我们提交一发:用时256ms, Treap常数自然小。
那么,还有没有更快的做法呢?
双向链表就可以解决这类允许离线的求前驱后继,先全部加上,在一个一个减去,思想很简单,功能也就不多了。
Treap:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 200005
#define INF 2000000000
using namespace std;
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;
}
inline int abs(int x) {return x>0?x:-x;}
int n, ans, a[MAXN];
struct Treap_Tree {
    int fa[MAXN], key[MAXN], sum[MAXN];
    int ch[MAXN][2], rad[MAXN];
    int Index, root;
    
    void DEBUG() {
        printf("root = %d\n", root);
        for(int i=0; i<=Index; i++) {
            printf("#    %d : \n", i);
            printf(" fa = %d\n", fa[i]);
            printf("key = %d\n", key[i]);
            printf("sum = %d\n", sum[i]);
            printf(" lc = %d, rc = %d\n", ch[i][0], ch[i][1]);
            printf("rad = %d\n", rad[i]);
        }
        puts("\n=============================================");
    }
    
    void Init() {
        srand(23333);
        Index = root = -1;
    }
    
    void Newnode(int p, int x, int f) {
        fa[p] = f; key[p] = x; sum[p] = 1;
        ch[p][0] = ch[p][1] = -1;
        rad[p] = rand() % 200000;
    }
    
    void Update(int p) {
        sum[p] = 1;
        if(ch[p][0] >= 0) sum[p] += sum[ch[p][0]];
        if(ch[p][1] >= 0) sum[p] += sum[ch[p][1]];
    }
    
    void rotate(int p, int d) {
        int f = fa[p]; fa[p] = fa[f];
        ch[f][d] = ch[p][d^1]; fa[ch[p][d^1]] = f;
        ch[p][d^1] = f; fa[f] = p;
        if(fa[p] < 0) root = p;
        else {
            if(ch[fa[p]][0] == f) ch[fa[p]][0] = p;
            else ch[fa[p]][1] = p;
        }
        Update(f); Update(p);
    }
    
    void Treap(int p) {
        while(fa[p]>=0 && rad[fa[p]]>rad[p]) {
            if(p == ch[fa[p]][0]) rotate(p, 0);
            else rotate(p, 1);
        }
    }
    
    void Insert(int x) {
        if(root < 0) {
            Index = root = 0;
            Newnode(root, x, -1);
            return;
        }
        int p = root, f;
        while(p >= 0) {
            f = p;
            if(x <= key[p]) p = ch[p][0];
            else p = ch[p][1];
        }
        int d; if(x <= key[f]) d=0; else d=1;
        ch[f][d] = ++Index;
        Newnode(ch[f][d], x, f);
        p=ch[f][d]; while(fa[p]>=0) {p=fa[p]; sum[p]++;}
        Treap(ch[f][d]);
    }
    
    int  Query_rank(int x) {
        int rank = 0, p = root;
        while(true) {
            if(x == key[p]) {
                rank++; if(ch[p][0]>=0) rank+=sum[ch[p][0]];
                return rank;
            }
            if(x <= key[p]) p = ch[p][0];
            else {
                rank++; if(ch[p][0]>=0) rank+=sum[ch[p][0]];
                p = ch[p][1];
            }
        }
    }
    
    int  Query_pos(int k) {
        if(k < 1 || k > sum[root]) return INF;
        int p = root;
        while(true) {
            int rank=1; if(ch[p][0]>=0) rank+=sum[ch[p][0]];
            if(rank == k) return key[p];
            if(k < rank) p = ch[p][0];
            else {
                k -= rank; p = ch[p][1];
            }
        }
    }
} T;

int main() {
    n = read();
    for(int i=1; i<=n; i++) a[i]=read();
    
    T.Init(); T.Insert(a[1]);
    ans = 0;
    for(int i=2; i<=n; i++) {
        T.Insert(a[i]);
        int cha = INF;
        int k = T.Query_rank(a[i]);
        for(int j=-2; j<=2; j++)
            if(j != 0) {
                int v = T.Query_pos(k+j);
                cha = min(cha, abs(a[i]-v));
            }
        ans += cha;
    }
    printf("%d\n", ans+a[1]);
    
    return 0;
}

双向链表:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 200005
#define INF 2000000000
using namespace std;
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;
}
int n, a[MAXN];
int pos[MAXN];
unsigned int ans;
inline int abs(int x) {return x>0?x:-x;}

struct Linked_List {
    struct Node {
        int key, pos;
        int pre, nex;
        bool operator < (const Node & rhs) const { return key<rhs.key; }
    } s[MAXN];
    
    void Build(int *a, int n) {
        for(int i=1; i<=n; i++) {
            s[i].key = a[i]; s[i].pos = i;
        }
        sort(s+1, s+n+1);
        for(int i=1; i<=n; i++) pos[s[i].pos] = i;
        s[1].nex=2; for(int i=2; i<n; i++) {s[i].pre=i-1;s[i].nex=i+1;} s[n].pre=n-1;
        s[1].pre = s[n].nex = -1;
    }
    
    void Delete(int p) {
        if(s[p].pre > 0)
            s[s[p].pre].nex = s[p].nex;
        if(s[p].nex > 0)
            s[s[p].nex].pre = s[p].pre;
        
    }
    
    int  Get_pre(int p) {
        if(s[p].pre > 0) return s[s[p].pre].key;
        else return INF;
    }
    
    int  Get_nex(int p) {
        if(s[p].nex > 0) return s[s[p].nex].key;
        else return INF;
    }
    
} LL;

int main() {
    n = read();
    for(int i=1; i<=n; i++) a[i]=read();
    LL.Build(a, n);
    ans = 0;
    for(int i=n; i>1; i--) {
        int pre = LL.Get_pre(pos[i]);
        int nex = LL.Get_nex(pos[i]);
        int cha = INF;
        cha = min(cha, abs(a[i]-pre));
        cha = min(cha, abs(a[i]-nex));
        ans += cha;
        LL.Delete(pos[i]);
    }
    printf("%d\n", ans+a[1]);
    return 0;
}