学步园

练习模板.

Splay是什么呢?

它可以保持元素的有序性,通过旋转的方式将最近插入的元素旋转到根部,在局部频繁访问的情况下可以提速.

支持删除,插入,求前驱后继,求第k大.等...

可以通过数组或指针的方式实现...实质是...唉,再做一些题再总结吧

#include<cstdio>
using namespace std;

const int MAXN = 111111;
const int INF = 1e9;

int min(int a, int b)
{
    int diff = b-a;
    return a + (diff & (diff>>31));
}
int max(int a,int b)
{
    int diff = b-a;
    return b - (diff & (diff>>31));
}
struct SplayTree///数组模拟
{
    int son[MAXN][2],far[MAXN],val[MAXN];
    int rt,size;
    void Link(int x,int y,bool c)
    {///将x作为y的c儿子连接上
        far[x]=y,son[y][c]=x;
    }
    void Rotate(int x,bool c)
    {///c = 1 Zig c = 0 Zag
        int y = far[x];
        Link(x,far[y],son[far[y]][1] == y);///如果y是右儿子,x也是;否则x是左儿子
        Link(son[x][c],y,!c);
        Link(y,x,c);
    }
    void Splay(int x,int g)
    {
        while(far[x]!=g)
        {
            int y = far[x];
            bool cy = son[far[y]][1] == y, cx = son[y][1] == x;
            if(far[y] == g)   Rotate(x,!cx);
            else
            {
                if(cx == cy)   Rotate(y,!cy);
                else   Rotate(x,!cx);
                Rotate(x,!cy);
            }
        }
        if(!g)  rt = x;
    }
    void NewNode(int y,int &x,int a)///y是父节点,x是新加节点,a为新加节点的值
    {
        x = ++size;///新加节点地址与size保持同步,它其实是一个指针O.O,命运就是被修改
        far[x] = y,val[x] = a;
        son[x][0] = son[x][1] = 0;
    }
    void Prepare()
    {
        NewNode(size = 0, rt, -INF);///第二个参数是引用,也就是传入函数之后可以被修改
        NewNode(rt, son[rt][1],INF);
    }
    void Insert(int a)
    {
        int x = rt;///val[x]<a就可以表示寻儿子的方向= =,总是靠近a
        while(son[x][val[x]<a])   x = son[x][val[x]<a];
        ///只要a>val[x]且右儿子不空,x就往右儿子移动直到空,左也一样
        NewNode(x, son[x][val[x]<a], a);
        Splay(size,0);///size就是目前新加节点的地址,下标
    }
    int Pre(int a)///前驱 <=a 的最大数
    {
        int x = rt,ret = -INF;
        while( x )///已经到了边界,没有儿子了,就返回最近的那个数
        {
            if(val[x] == a)   return a;///如果找到了相等的,直接返回
            if(val[x]<a)    ret = max(ret,val[x]);
            x = son[x][val[x]<a];
        }
        return ret;
    }
    int Suc(int a)///后继 >=a 的最小数
    {
        int x = rt,ret = INF;
        while( x )
        {
            if(val[x] == a)     return a;
            if(val[x]>a)        ret = min(ret,val[x]);
            x = son[x][val[x]<a];///这里还是<,因为要最靠近a,但是不影响ret,
            ///因为只有>a才会被更新,且总是取最小值,最小值得以保留
        }
        return ret;
    }
}spt;
int i,j,a,n,ans;
int main()
{
    scanf("%d%d",&n,&a);
    ans = a;
    spt.Prepare();///初始化
    spt.Insert( a );
    while(--n)
    {
        if(!(~scanf("%d",&a)))  a = 0;
        ans += min( a - spt.Pre(a), spt.Suc(a) - a );///求前驱与后继
        spt.Insert( a );///插入操作
    }
    printf("%d\n",ans);
    return 0;
}