bzoj1588

splay

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct data

{

    int fa,l,r,size,cnt,key;

}tree[];

bool flag1,flag2;

int root,n,tot,ans,a,b;

int abs(int x)

{

    return x>?x:-x;

}

void update(int x)

{

    tree[x].size=tree[tree[x].l].size+tree[tree[x].r].size+tree[x].cnt;

}

void zig(int x)

{

    int y=tree[x].fa;

    int z=tree[x].r;

    tree[y].l=z;

    tree[z].fa=y;

    tree[x].fa=tree[y].fa;

    if(y==tree[tree[y].fa].l) tree[tree[y].fa].l=x;

    else tree[tree[y].fa].r=x;

    tree[x].r=y;

    tree[y].fa=x;

    update(x);

    update(y);

}

void zag(int x)

{

    int y=tree[x].fa;

    int z=tree[x].l;

    tree[y].r=z;

    tree[z].fa=y;

    tree[x].fa=tree[y].fa;

    if(y==tree[tree[y].fa].l) tree[tree[y].fa].l=x;

    else tree[tree[y].fa].r=x;

    tree[x].l=y;

    tree[y].fa=x;

    update(x);

    update(y);

}

void splay(int x)

{

    if(!root)

    {

        root=x;

        return;

    }

    while(tree[x].fa)

    {

        int y=tree[x].fa;

        int z=tree[y].fa;

        if(y==root)

        {

            if(x==tree[root].l) zig(x); else zag(x);

            update(x);

            break;

        }

        else if(y==tree[z].l&&x==tree[y].l) {zig(y); zig(x);}

        else if(y==tree[z].r&&x==tree[y].r) {zag(y); zag(x);}

        else if(y==tree[z].l&&x==tree[y].r) {zag(x); zig(x);}

        else if(y==tree[z].r&&x==tree[y].l) {zig(x); zag(x);}

        update(x);

    }

    root=x;

}

void insert(int x,int k)

{

    if(tree[x].key<k)

    {

        if(tree[x].r==)

        {

            ++tot;

            tree[tot].fa=x;

            if(x) tree[x].r=tot;

            tree[tot].key=k;

            tree[tot].cnt=;

            update(tot);

            update(x);

            splay(tot);

            return;

        }

        insert(tree[x].r,k);

        update(x);

    }

    else

    {

        if(tree[x].l==)

        {

            ++tot;

            tree[tot].fa=x;

            if(x) tree[x].l=tot;

            tree[tot].key=k;

            tree[tot].cnt=;

            update(tot);

            update(x);

            splay(tot);

            return;

        }

        insert(tree[x].l,k);

        update(x);

    }

}

void findnxt(int x,int k,int pd)

{

    if(x==) return;

    if(pd==)

    {

        if(tree[x].key<=k)

        {

            flag1=true;

            a=tree[x].key;

            findnxt(tree[x].r,k,pd);

        } else findnxt(tree[x].l,k,pd);

    }

    else

    {

        if(tree[x].key>=k)

        {

            flag2=true;

            b=tree[x].key;

            findnxt(tree[x].l,k,pd);

        } else findnxt(tree[x].r,k,pd);

    }

}

int main()

{

    scanf("%d",&n);

    while(n--)

    {

        int x; scanf("%d",&x);

        findnxt(root,x,);

        findnxt(root,x,);

        int temp=;

        bool flag=false;

//        printf("%d %d\n",a,b);

        if(flag1)

        {

            temp=abs(a-x);

            flag=true;

        }

        if(flag2)

        {

            if(flag) temp=min(temp,abs(b-x));

            else temp=abs(b-x);

        }

        if(tree[root].size==) ans+=x;

        else ans+=temp;

        insert(root,x);

        flag1=false;

        flag2=false;

        a=;

        b=;

    }

    printf("%d",ans);

    return ;

}