bzoj 1588 splay模板题

用晚自习学了一下splay模板，没想象中那么难，主要是左旋和右旋可以简化到一个函数里边，减少代码长度。。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define maxn 33333

 #define inf 0x3f3f3f3f

 #define lc(x) ch[(x)][0]

 #define rc(x) ch[(x)][1]

 using namespace std;

 int fa[maxn],ch[maxn][],root,k[maxn],ind=;

 inline void rotate(int p)

 {

    int q=fa[p],y=fa[q],x=ch[q][]==p;

    ch[q][x]=ch[p][x^];fa[ch[q][x]]=q;

    ch[p][x^]=q;fa[q]=p;

    fa[p]=y;

    if(y)

    {

        if(ch[y][]==q)ch[y][]=p;

        else ch[y][]=p;

    }

 }

 inline void splay(int x)

 {

     for(int y;y=fa[x];rotate(x))

     {

         if(fa[y])

         {

             if(y==lc(fa[y])&&x==lc(y)||(y==rc(fa[y])&&x==rc(y)))rotate(y);

             else rotate(x);

         }

     }

     root=x;

 }

 void insert(int x,int v)

 {

      while(ch[x][k[x]<v])x=ch[x][k[x]<v];

      ch[x][k[x]<v]=++ind;

      fa[ind]=x;k[ind]=v;splay(ind);

 }

 inline int pre(int x)

 {

     int tmp=ch[x][];

     while(ch[tmp][])tmp=ch[tmp][];

     return k[tmp];

 }

 inline int suc(int x)

 {

     int tmp=ch[x][];

     while(ch[tmp][])tmp=ch[tmp][];

     return k[tmp];

 }

 int main()

 {

     int t;int n;

     int ans=;

     scanf("%d",&n);

     if(scanf("%d",&t)==-)t=;

     root=;k[root]=t;

     ans=t;

     insert(root,inf);insert(root,-inf);

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

     {

         if(scanf("%d",&t)==-)t=;

         insert(root,t);

         int a=pre(root);int b=suc(root);

         ans+=min(t-a,b-t);

     }

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

     return ;

 }