C++ :

#include<bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1e5+99;
const int INF = 0x3f3f3f3f;
 
 
struct spalytree
{
    int ch[maxn][2],pre[maxn],sz[maxn],key[maxn],root,tot1;
    void Rotate(int x,int d)
    {
        int y = pre[x];
        ch[y][!d] = ch[x][d];
        pre[ch[x][d]]=y;
        if(pre[y])ch[pre[y]][ch[pre[y]][1]==y] = x;
        pre[x] = pre[y];
        ch[x][d] = y;
        pre[y] = x;
    }
 
    void splay(int r,int goal)
    {
        while(pre[r]!=goal)
        {
            if(pre[pre[r]] == goal)
                Rotate(r,ch[pre[r]][0] ==r);
            else
            {
                int y =  pre[r];
                int d = ch[pre[y]][0] ==y;
 
                if(ch[y][d] == r)
                {
                    Rotate(r,!d);
                    Rotate(r,d);
                }
                else
                {
                    Rotate(y,d);
                    Rotate(r,d);
                }
            }
        }
        if(goal == 0) root = r;
    }
 
    void newnode(int &r,int fa,int k)
    {
        r = ++tot1;
        sz[r] = 1;//不需要
        key[r] = k;
        pre[r] = fa;
        ch[r][0] = ch[r][1] = 0;
    }
    /**建立排序树*/
    int insert(int k)/**插入一个值为k的节点，insert一个一个的写*/
    {
        int r = root;
        while(1)
        {
            if(key[r]==k)
            {
                splay(r,0);
                return 0;
            }
            else if(k<key[r])
            {
                if(ch[r][0])r = ch[r][0];
                else
                {
                    newnode(ch[r][0],r,k);
                    splay(ch[r][0],0);
                    return 1;
                }
            }
            else if(k>key[r])
            {
                if(ch[r][1])r=ch[r][1];
                else
                {
                    newnode(ch[r][1],r,k);
                    splay(ch[r][1],0);
                    return 1;
                }
            }
        }
    }
 
    
   /**找前面出现的最接近这个值的，从比他大的找最小的，从比他小的找最大的，然后去判断这两个值哪个更接近他*/
    int get_pre(int x)
    {
        int r = ch[x][0];
        if(r==0)return INF;
        while(ch[r][1])r = ch[r][1];
        return key[x] - key[r];
    }
 
    int get_next(int x)
    {
        int r = ch[x][1];
        if(r==0)return INF;
        while(ch[r][0])r = ch[r][0];
        return key[r]-key[x];
    }
 
 
}st;
 
 
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        st.root = st.tot1 = 0;
        int ans = 0;
        for(int i=1; i<=n; i++)
        {
            int num;
            if(scanf("%d",&num)==EOF)num = 0;
            if(i==1)
            {
                ans+=num;
                st.newnode(st.root,0,num);
                continue;
            }
            if(st.insert(num)==0)continue;
            int a = st.get_pre(st.root);
            int b = st.get_next(st.root);
            ans += min(a,b);
        }
        printf("%d\n",ans);
    }
}

要抄题解的看我

#include <bits/stdc++.h>
using namespace std;
#define inf 2100000000
#define maxn 100010
int ch[maxn][2],f[maxn],size[maxn],key[maxn],lazy[maxn];
int sz,root;
int read() {
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
bool get(int x) {return ch[f[x]][1]==x;}
void update(int x) {
    if(x) {
        size[x]=1;
        if(ch[x][0]) size[x]+=size[ch[x][0]];
        if(ch[x][1]) size[x]+=size[ch[x][1]];
    }
    return ;
}
void pushdown(int x) { //push down lazy tag
    if(x && lazy[x]) {
        lazy[ch[x][0]]^=1;
        lazy[ch[x][1]]^=1;
        swap(ch[x][0],ch[x][1]);
        lazy[x]=0;
    }
    return ;
}
void rotate(int x) {
    int old=f[x],oldf=f[old],whichx=get(x);
    pushdown(old);
    pushdown(x);
    ch[old][whichx]=ch[x][whichx^1];
    f[ch[old][whichx]]=old;
    ch[x][whichx^1]=old;
    f[old]=x;
    f[x]=oldf;
    if(oldf)
        ch[oldf][ch[oldf][1]==old]=x;
    update(old);
    update(x);
    return ;
}
void splay(int x,int tar) { //rotate x to tar
    for(int fa;(fa=f[x])!=tar;rotate(x))
        if(f[fa]!=tar)
            rotate(get(x)==get(fa)?fa:x);
    if(!tar)
        root=x;
    return ;
}
int findx(int x) { //by search the ranking return the treenumber
    int now=root;
    while(1) {
        pushdown(now);
        if(ch[now][0]&&x<=size[ch[now][0]])
            now=ch[now][0];
        else {
            int tmp=(ch[now][0]?size[ch[now][0]]:0)+1;
            if(x<=tmp) return now;
            x-=tmp;
            now=ch[now][1];
        } 
    }
}
void insert(int x) {
    if(root==0) {
        sz++;
        ch[sz][0]=ch[sz][1]=f[sz]=0;
        root=sz;
        size[sz]=1;
        key[sz]=x;
        return ;
    }
    int now=root,fa=0;
    while(1) {
        if(x==key[now]) {
            update(now);
            update(fa);
            splay(now,0);
            break;
        }
        fa=now;
        now=ch[now][key[now]<x];
        if(now==0) {
            sz++;
            ch[sz][0]=ch[sz][1]=0;
            f[sz]=fa;
            size[sz]=1;
            ch[fa][key[fa]<x]=sz;
            key[sz]=x;
            update(fa);
            splay(sz,0);
            break;
        }
    }
    return ;
}
void print(int x) {
    pushdown(x);
    if(ch[x][0])
        print(ch[x][0]);
    if(key[x]!=inf && key[x]!=-inf)
        printf("%d ",key[x]);
    if(ch[x][1])
        print(ch[x][1]);
    return ;
}
int main() {
    int n,m,l,r;
    n=read(),m=read();
    insert(-inf);
    for(int i=1;i<=n;i++)
        insert(i);
    insert(inf);
    for(int i=1;i<=m;i++) {
        l=read(),r=read();
        l=findx(l);
        r=findx(r+2);
        splay(l,0);
        splay(r,l);
        lazy[ch[ch[root][1]][0]]^=1;
    }
    print(root);
    return 0;
}