Spaly 상세 설명

    #include
    using namespace std;
    struct sd
    {
        int value;//          
        int son[2];//     
        int delta; //    
        int father;//      
        int below;//         
    }tree[1000005];
    int root;//  
    int cnt;//     
    int dir;//     0    1    
    inline void maintain(int now)//            （        ）
    {
        tree[now].below=1;
        if(tree[now].son[0])tree[now].below+=tree[tree[now].son[0]].below;
        if(tree[now].son[1])tree[now].below+=tree[tree[now].son[1]].below;
    }
    inline int get(int now)//       
    {
        if(tree[tree[now].father].son[0]==now)return 0;
        return 1;
    }
    //---------------------------------------------------------------------- 
    void rotate(int now)//          
    {
        dir=get(now);
        int fa=tree[now].father,gra=tree[fa].father;
        tree[fa].son[dir]=tree[now].son[dir^1];
        tree[tree[now].son[dir^1]].father=fa;
        if(gra)tree[gra].son[get(fa)]=now;
        tree[now].father=gra;
        tree[fa].father=now;
        tree[now].son[dir^1]=fa;
        maintain(fa);
        maintain(now);
    }
    //---------------------------------------------------------------------- 
    inline void splay(int now)
    {
        int gra,fat;//  now       
        int opt1,opt2;//         
        while(tree[now].father)//  now       ， now         。  ！ 
        {
            fat=tree[now].father;gra=tree[fat].father;
            if(gra!=0)//     ，      ！ 
            {
                opt1=get(now);opt2=get(fat);
                if(opt1==opt2){rotate(fat),rotate(now);}
                else{rotate(now),rotate(now);}
            }
            else
            rotate(now);
        }
        root=now;//      
    }
    void insertit(int now,int val,int pre)
    {
        if(!now)//  now  （    ，     ）     （  ）  ，   ，         
        {
            cnt++;
            tree[cnt].father=pre;
            tree[cnt].value=val;
            tree[cnt].below=1;
            if(tree[pre].value>val)tree[pre].son [0]=cnt;
            else tree[pre].son[1]=cnt;
            splay(cnt);
        }
        else//  now    
        {
            if(tree[now].value>val)insertit(tree[now].son[0],val,now);
            else insertit(tree[now].son[1],val,now);
        }
    }
    inline void in(int &x)//   
    {
        bool fu=false;
        x=0;char c=getchar();
        while(!isdigit(c))
            {
            if(c=='-')
            {
                fu=true;
            }
            c=getchar();}
        while(isdigit(c)){x*=10,x+=c-48;c=getchar();}
        if(fu)x*=-1;
    }
    int find_pre(int now)//     
    {
        if(!now)return -99999999;//         
        if(tree[now].son[1])return find_pre(tree[now].son[1]);
        //          ，             （  ） 
        return tree[now].value;
        //        ，      
    }
    int find_suc(int now)//     
    {
        if(!now)return 99999999;//         
        if(tree[now].son[0])return find_suc(tree[now].son[0]);
        //          ，             （  ） 
        return tree[now].value;
        //        ，      
    }
    int main()
    {
        long long tot=0;
        int num,prev,sucv;
        in(num);
        int a;
        while(num--)
        {
            in(a);
            insertit(root,a,root);//  （        ） 
            prev=find_pre(tree[root].son[0]);//    （   ） 
            sucv=find_suc(tree[root].son[1]);//   （   ） 
            if(sucv==99999999&&prev==-99999999)//           
            {
                tot+=a;
                continue;
            }
            if(a-prev>sucv-a)tot+=sucv-a;//         ，     
            else tot+=a-prev;//     
        }
        printf("%lld",tot);//     
        return 0;
}