HNOI2002

对于当天的营业额，你要找到之前的数和他差的绝对值最小的和。由于这个是不断在插入的，所以用伸展树来维护。

http://www.lydsy.com/JudgeOnline/problem.php?id=1588

照着kuangbin大牛的代码敲下来的。

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define INF 99999999

#define ll __int64

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN = ;

int pre[MAXN],key[MAXN],ch[MAXN][],root,tot;

//父亲结点 键值 左右子树 根节点 节点数量

int n;

void Newnode(int &rt,int pa,int k)

{

    rt = ++tot;

    pre[rt] = pa;

    key[rt] = k;

    ch[rt][] = ch[rt][] = ;//空

}

void Rotate(int x,int kind)

{

    int y = pre[x];

    ch[y][!kind] = ch[x][kind];

    pre[ch[x][kind]] = y;

    if(pre[y]){

        ch[pre[y]][ch[pre[y]][]==y] = x;

    }

    pre[x] = pre[y];

    ch[x][kind] = y;

    pre[y] = x;

}

//将结点rt 调整到goal下面

void splay(int rt,int goal)

{

    while(pre[rt] != goal)

    {

        if(pre[pre[rt]] == goal)

            Rotate(rt,ch[pre[rt]][]==rt);

        else {

            int y = pre[rt];

            int kind = (ch[pre[y]][]==y);

            if(ch[y][kind] == rt){//rt 和 pre[rt]不在同一方向上

                Rotate(rt,!kind); //kind=1时，说明rt在y的右边 而y在pre[y]的左边

                Rotate(rt,kind);

            }

            else {

                Rotate(y,kind);

                Rotate(rt,kind);

            }

        }

    }

    if(goal == )

        root = rt;

}

int Insert(int k)

{

    int rt = root;

    while(ch[rt][key[rt]<k]){//如果key[r]<k，表明当前k在右边，不然去左边

        if(key[rt] == k){

            splay(rt,);

            return ;

        }

        rt = ch[rt][key[rt]<k];

    }

    Newnode(ch[rt][key[rt]<k],rt,k);

    splay(ch[rt][key[rt]<k],);

    return ;

}

int get_pre(int rt)

{

    int tmp = ch[rt][];

    if(tmp == )

        return INF;

    while(ch[tmp][])

    {

        tmp = ch[tmp][];

    }

    return key[rt] - key[tmp];

}

int get_next(int rt)

{

    int tmp = ch[rt][];

    if(tmp == )

        return INF;

    while(ch[tmp][])

    {

        tmp = ch[tmp][];

    }

    return key[tmp] - key[rt];

}

int main()

{

    int i,j;

    while(~scanf("%d",&n))

    {

        root = tot = ;

        int ans = ;

        for(i=; i<=n; i++){

            int num;

            if(scanf("%d",&num)==EOF)num = ;

            if(i == ){

                ans += num;

                Newnode(root,,num);

                continue;

            }

            if(Insert(num) == )

                continue;

            int a = get_pre(root);

            int b = get_next(root);

            //cout<<a<<" "<<b<<endl;

            ans += min(a,b);

        }

        printf("%d\n",ans);

    }

}