BZOJ-1588

第一次写splay，还是写复杂一点吧，左旋右旋都写，不然过几天自己都看不懂了。。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
typedef long long ll;
using namespace std;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
const int N=500005;
int fa[N],c[N],ch[N][2],x,n,i,idn,ans,root;
void look(int i)
{
    if (i==0) return;
    look(ch[i][0]);
    printf("%d ",c[i]);
    look(ch[i][1]);
}
void zag(int x)
{
    int y=fa[x],z=fa[y];
    ch[y][1]=ch[x][0]; fa[ch[y][1]]=y;
    ch[x][0]=y; fa[y]=x;
    fa[x]=z;
    if (z)
        if (ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;
}
void zig(int x)
{
    int y=fa[x],z=fa[y];
    ch[y][0]=ch[x][1]; fa[ch[y][0]]=y;
    ch[x][1]=y; fa[y]=x;
    fa[x]=z;
    if (z)
        if (ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;
}
void splay(int x)
{
    while(fa[x])
    {
        int y=fa[x],z=fa[y];
        if (!z)
            if (ch[y][0]==x) zig(x);else zag(x);
        else
        {
            if (ch[z][0]==y)
                if (ch[y][0]==x) zig(y),zig(x);
                else zag(x),zig(x);
            else
                if (ch[y][0]==x) zig(x),zag(x);
                else zag(y),zag(x);
        }
    }
    root=x;
}
void ins(int x,int v)
{
    int nxt;
    if (v<c[x]) nxt=0;else nxt=1;
    while(ch[x][nxt])
    {
        x=ch[x][nxt];
        if (v<c[x]) nxt=0;else nxt=1;
    }
    idn++; ch[x][nxt]=idn; fa[idn]=x; c[idn]=v;
    //look(1);
    splay(idn);
    //look(1);
}
int pre(int x)
{
    int tmp=ch[x][0];
    while(ch[tmp][1]) tmp=ch[tmp][1];
    return c[tmp];
}
int suc(int x)
{
    int tmp=ch[x][1];
    while(ch[tmp][0]) tmp=ch[tmp][0];
    return c[tmp];
}
int main()
{
    scanf("%d",&n);
    idn=1,c[1]=-2000000000; root=1;
    ins(root,2000000000);
    for (i=1;i<=n;i++)
    {
        if (scanf("%d",&x)==-1) x=0;
        if (i==1) ans+=x,ins(root,x);
        else ins(root,x),ans+=min(x-pre(root),suc(root)-x);
        //look(root);printf("\n");
    }
    printf("%d",ans);
}