BZOJ3224 普通平衡樹 Splay + 替罪羊樹

大家都很強， 可與之共勉。

Splay：

Splay的優勢是進行序列中的區間操作。是以才維護一個普通序列的時候它其實是會被卡成一條鍊的，是以最好操作一次之後就把這個節點splay到根。

至于splay怎麼做，就是很常見的雙旋處理了。

注意到為了防止出現假的節點，一定要在erase的時候把root改了而不是改形式參數。不然這個代碼就是錯的了（但是可以A）。

/**************************************************************
    Problem: 
    User: Lazer2001
    Language: C++
    Result: Accepted
    Time: ms
    Memory: kb
****************************************************************/

# include <bits/stdc++.h>

namespace In  {
# define In_Len 2000000
    static std :: streambuf *fb ( std :: cin.rdbuf ( ) ) ;
    static char buf [In_Len], *ss (  ), *tt (  ) ;
# define pick( )  ( (ss == tt) ? ( tt = buf + fb -> sgetn ( ss = buf, In_Len ), ((ss == tt) ? -1 : *(ss ++)) ) :*(ss ++) )

    inline char getc ( )  {  register char c; while ( ! isalpha ( c = pick ( ) ) ) ;  return c ;  }

    inline int read ( )  {
        register int x, c ;
        bool opt (  ) ;
        while ( ! isdigit ( c = pick ( ) ) && ( c ^ - ) && ( c ^  ) ) ;
        if ( c ==  )  c = pick ( ), opt =  ;
        for ( x = - + c ; isdigit ( c = pick ( ) ) ; ( x *=  ) += c -  ) ;
        return opt ? x : -x ;
    }
# undef pick
# undef In_Len
}

# define N 100010

class Splay  {
    private :
        struct node  {
            int val, siz, same ;
            node *ch [], *fa ;
            inline void update ( )  {
                siz = ch [] -> siz + ch [] -> siz + same ;
            }
        } pool [N << ], *null, *root ;

        inline node* newnode ( node* fa, const int& val )  {
            static node* tp ( pool +  ) ;
            tp -> val = val, tp -> siz = tp -> same =  ;
            return tp -> ch [] = tp -> ch [] = null, tp -> fa = fa, tp ++ ;
        }

        # define isrs( p )  ( p == p -> fa -> ch [1] )

        inline void rotate ( node* p )  {
            node* fa = p -> fa ;
            bool d ( isrs ( p ) ) ;
            fa -> ch [d] = p -> ch [! d] ;
            if ( p -> ch [! d] != null )  p -> ch [! d] -> fa = fa ;
            p -> fa = fa -> fa ;
            if ( fa -> fa != null )  fa -> fa -> ch [isrs ( fa )] = p ;
            p -> ch [! d] = fa ;
            fa -> fa = p ;
            fa -> update ( ) ; p -> update ( ) ;
        }

        inline void splay ( node* p, node* tar )  {
            while ( p -> fa != tar )  {
                if ( isrs ( p ) == isrs ( p -> fa ) && p -> fa -> fa != tar )  rotate ( p -> fa ) ;
                rotate ( p ) ;
            }
            if ( tar == null )  root = p ;
        }

        # undef isrs

        inline void display ( node*& nd )  {
            if ( nd == null )  return ;
            display ( nd -> ch [] ) ;
            printf ( "val: %d same: %d\n", nd -> val, nd -> same ) ;
            assert ( nd -> siz == nd -> ch [] -> siz + nd -> ch [] -> siz + nd -> same ) ;
            display ( nd -> ch [] ) ;
        }
    public :

        Splay ( )  {
            root = null = pool ;
            null -> val = null -> siz = null -> same = , null -> ch [] = null -> ch [] = null -> fa = null ;
        }

        inline void insert ( int val )  {
            if ( root == null )  {
                root = newnode ( null, val ) ;
                return ;
            }
            node* nd = root ;
            for ( ; ; )  {
                if ( val == nd -> val )  return ( void )  ++ nd -> same, ( void ) ++ nd -> siz, splay ( nd, null ) ;  // splay !!!
                if ( nd -> ch [val > nd -> val] == null )  break ;
                nd = nd -> ch [val > nd -> val] ;
            }
            nd -> ch [val > nd -> val] = newnode ( nd, val ) ;
            nd -> update ( ) ;
            splay ( nd, null ) ;
        }

        inline void erase ( int val )  {
            node* nd = root ;
            for ( ; ; )  {
                if ( val == nd -> val )  break ;
                nd = nd -> ch [val > nd -> val] ;
            }
            splay ( nd, null ) ;
            if ( -- nd -> same )  return ;

            node *ls = nd -> ch [], *rs = nd -> ch [] ;
            if ( ls == null && rs == null )  {
                if ( nd -> same ==  )  root = null ;
                return ;
            }
            if ( ls == null )  {
                if ( nd -> same ==  )  root = nd -> ch [], root -> fa = null ;
                return ;
            }
            if ( rs == null )  {
                if ( nd -> same ==  )  root = nd -> ch [], root -> fa = null ;
                return ;
            }
            if ( nd -> same ==  )  {
                node *pre = ls, *pro = rs ;
                while ( pre -> ch [] != null )  pre = pre -> ch [] ;
                while ( pro -> ch [] != null )  pro = pro -> ch [] ;
            //  assert ( pro != null && pre != null ) ;
                splay ( pre, null ) ;
                splay ( pro, pre ) ;
                pro -> ch [] = null ; // is nd ;
                pro -> update ( ) ;
                pre -> update ( ) ;
            }
        }

        inline int kth ( int k )  {
            node* nd = root ;
            for ( ; ; )  {
                if ( k <= nd -> ch [] -> siz )  {
                    nd = nd -> ch [] ;
                }  else if ( k <= nd -> ch [] -> siz + nd -> same )  {
                    return nd -> val ;
                }  else k -= nd -> ch [] -> siz + nd -> same, nd = nd -> ch [] ;
            }
        }

        inline int rank ( int val )  {
            node* nd = root ;
            int rt (  ) ;
            while ( nd != null )  {
                if ( val > nd -> val )  {
                    rt += nd -> ch [] -> siz + nd -> same ;
                    nd = nd -> ch [] ;
                }  else  nd = nd -> ch [] ;
            }
            return rt ;
        }

        inline int prev ( int val )  {
            node* nd = root ;
            int rt ( INT_MIN ) ;
            while ( nd != null )  {
                if ( nd -> val < val )  {
                    rt = nd -> val ;
                    nd = nd -> ch [] ;
                }  else nd = nd -> ch [] ;
            }
            return rt ;
        }

        inline int prov ( int val )  {
            node* nd = root ;
            int rt ( INT_MAX ) ;
            while ( nd != null )  {
                if ( nd -> val > val )  {
                    rt = nd -> val ;
                    nd = nd -> ch [] ;
                }  else nd = nd -> ch [] ;
            }
            return rt ;
        }

        inline void display ( )  {
            display ( root ) ;
        }
} S ;

# undef N

//# define ZJC_LOCAL

int main ( )  {
# ifdef ZJC_LOCAL
    freopen ( "in.txt", "r", stdin ) ;
    freopen ( "out.txt", "w", stdout ) ;
# endif
    for ( int M = In :: read ( ) ; M ; -- M )  {
        switch ( In :: read ( ) )  {
            case  :    S.insert ( In :: read ( ) ) ;  break ;
            case  :    S.erase ( In :: read ( ) ) ;  break ;
            case  :    printf ( "%d\n", S.rank ( In :: read ( ) ) ) ;  break ;
            case  :    printf ( "%d\n", S.kth ( In :: read ( ) ) ) ;  break ;
            case  :    printf ( "%d\n", S.prev ( In :: read ( ) ) ) ;  break ;
            case  :    printf ( "%d\n", S.prov ( In :: read ( ) ) ) ;  break ;
        }
    }
//  S.display ( ) ;
}
           

替罪羊樹：

替罪羊樹是跑得最快的

替罪羊樹的思想就是暴力重構，他不旋轉，隻要不平衡我就暴力重構，至于為什麼叫替罪羊，大概就是一個點不平衡了整棵樹就要重構吧。（複雜度可以證明是logn的）

設一個平衡因子，隻要以這個節點為根的一個子樹大小/以這個節點為根的樹的大小>平衡因子，我就把這個節點為根的樹直接O (n)重構。複雜度在均攤上是有保證的。

注意到替罪羊樹裡面一定是有假節點的（這個點的val已經被删除了）（因為不可以旋轉），是以不能像上面的Splay的操作那樣求前驅後繼，如果這個數曾經出現過的前驅被删掉了，那麼有可能你的曾經的前驅還沒有被重構，就沒有被删除。這樣以前的求法就有問題。是以通過排名+第k大來求。

平衡因子最好在0.5-1之間（一般0.75左右最優）看這個實驗

（這道題我試了0.70最優）

還有對于重構節點的傳參一定要是指針，不然你改不了實際的值（解引用可以）。

/**************************************************************
    Problem: 3224
    User: Lazer2001
    Language: C++
    Result: Accepted
    Time:176 ms
    Memory:8332 kb
****************************************************************/

# include <bits/stdc++.h>

namespace In  {
# define In_Len 2000000
    static std :: streambuf *fb ( std :: cin.rdbuf ( ) ) ;
    static char buf [In_Len], *ss (  ), *tt (  ) ;
# define pick( )  ( (ss == tt) ? ( tt = buf + fb -> sgetn ( ss = buf, In_Len ), ((ss == tt) ? -1 : *(ss ++)) ) :*(ss ++) )

    inline char getc ( )  {  register char c; while ( isspace ( c = pick ( ) ) ) ;  return c ;  }

    inline int read ( )  {
        register int x, c ;
        bool opt (  ) ;
        while ( isspace ( c = pick ( ) ) && ( c ^ - ) ) ;
        if ( c ==  )  c = pick ( ), opt =  ;
        for ( x = - + c ; isdigit ( c = pick ( ) ) ; ( x *=  ) += c -  ) ;
        return opt ? x : -x ;
    }
# undef pick
# undef In_Len
}

namespace Out  {
# define Out_Len 2000000
    std :: streambuf *fb ( std :: cout.rdbuf ( ) ) ;
    char buf [Out_Len], *ss ( buf ), *tt ( buf + Out_Len ) ;
# define echo( c )  ( (ss == tt) ? ( fb -> sputn ( ss = buf, Out_Len ), *ss ++ = c ) : ( *ss ++ = c ) )
    inline void putc ( char c )  {  echo ( c ) ;  }

    inline void print ( register int x )  {
        static int st [], tp (  ) ;
        if ( ! x )  {  echo (  ) ; return ;  }
        if ( x <  )  {  echo (  ) ; x = -x ;  }
        while ( x ) st [++ tp] = x %  | , x /=  ;
        while ( tp )  {  echo ( st [tp] ) ; -- tp ;  }
    }

    inline void flush ( )  {  fb -> sputn ( buf, ss - buf ) ;  }

# undef echo
# undef Out_Len
}

# define N 100010

template < class T >
class Stack  {
    private :
        int tp ;
        T s [N << ] ;
    public :
        Stack ( )  {  tp =  ;  }
        inline void clear ( )  {
            tp =  ;
        }
        inline T& top ( )  {
            return s [tp] ;
        }
        inline void pop ( )  {
            -- tp ;
        }
        inline void push ( const T& ele )  {
            s [++ tp] = ele ;
        }
        inline bool empty ( )  {
            return tp ==  ;
        }
        inline void reverse ( )  {
            std :: reverse ( s + , s + tp +  ) ;
        }
        inline int size ( )  {
            return tp ;
        }
} ;

class ScapeGoatTree  {
    private :
# define ALPHA 0.7
        struct node  {
            int val, siz, same ;
            node* ch [] ;
            inline void update ( )  {
                siz = ch [] -> siz + ch [] -> siz + same ;
            }
            inline bool unbalanced ( )  {
                return ( ch [] -> siz > siz * ALPHA ) || ( ch [] -> siz > siz * ALPHA ) ;
            }
        } pool [N << ], *null, *root, **rec_root, *rec [N] ; // **rec_root!!!
# undef ALPHA

        int rcnt ;
        Stack < node* >  s ;

        inline node* newnode ( int val )  {
            static node* tp ;
            tp = s.top ( ) ; s.pop ( ) ;
            tp -> val = val, tp -> siz = tp -> same =  ;
            return tp -> ch [] = tp -> ch [] = null, tp ;
        }

        inline void recycle ( node*& p )  {
            if ( p == null )  return ;
            recycle ( p -> ch [] ) ;
            if ( p -> same ==  ) s.push ( p ) ; else rec [++ rcnt] = p ;
            recycle ( p -> ch [] ) ;
        }

        inline node* build ( int lf, int rg )  {
            if ( lf > rg )  return null ;
            int mid = ( lf + rg ) >>  ;
            node* p = rec [mid] ;
            p -> ch [] = build ( lf, mid -  ) ;
            p -> ch [] = build ( mid + , rg ) ;
            p -> update ( ) ;
            return p ;
        }

        inline void rebuild ( node*& rec_root )  {
            rcnt =  ;
            recycle ( rec_root ) ; rec_root = build ( , rcnt ) ;
        }

        inline void insert ( node*& p, const int& val )  {  // recursion
            if ( p == null )  {
                p = newnode ( val ) ;
                return ;
            }
            ++ p -> siz ;
            if ( val == p -> val )  return ( void ) ++ p -> same ;
            insert ( p -> ch [val > p -> val], val ) ;
            if ( p -> unbalanced ( ) )  rec_root = &p ;
        }

        inline void erase ( node*& p, const int& val )  {
            -- p -> siz ;
            if ( p -> val == val )  {
                return ( void ) -- p -> same ; // if same == 0, it will delete in recycle ; 
            }
            erase ( p -> ch [val > p -> val], val ) ;
            if ( p -> unbalanced ( ) )  rec_root = &p ;
        }

        inline void display ( node*& nd )  {
            if ( nd == null )  return ;
            display ( nd -> ch [] ) ;
            printf ( "val: %d same: %d\n", nd -> val, nd -> same ) ;
            assert ( nd -> siz == nd -> ch [] -> siz + nd -> ch [] -> siz + nd -> same ) ;
            display ( nd -> ch [] ) ;
        }

    public :

        ScapeGoatTree ( )  {
            root = null = pool ;
            null -> val = null -> siz = , null -> ch [] = null -> ch [] = null ;
            for ( register int i =  ; i < N <<  ; ++ i )  s.push ( pool + i ) ; 
        }

        inline void insert ( int val )  {
            rec_root = &null ;
            insert ( root, val ) ;
            if ( *rec_root != null )  rebuild ( *rec_root ) ;
        }

        inline void erase ( int val )  {
            rec_root = &null ;
            erase ( root, val ) ;
            if ( *rec_root != null )  rebuild ( *rec_root ) ;
        }

        inline int kth ( int k )  {
            node* nd = root ;
            for ( ; ; )  {
                if ( k <= nd -> ch [] -> siz )  {
                    nd = nd -> ch [] ;
                }  else if ( k <= nd -> ch [] -> siz + nd -> same )  {
                    return nd -> val ;
                }  else k -= nd -> ch [] -> siz + nd -> same, nd = nd -> ch [] ;
            }
        }

        inline int rank ( int val )  {
            node* nd = root ;
            int rt (  ) ;
            while ( nd != null )  {
                if ( val > nd -> val )  {
                    rt += nd -> ch [] -> siz + nd -> same ;
                    nd = nd -> ch [] ;
                }  else  nd = nd -> ch [] ;
            }
            return rt ;
        }

        inline int prev ( int val )  {   // 因為有些節點same為0，但是還在樹中(删除的時候沒有真正删除)，是以不能直接周遊樹中的val來求，而是隻能通過排名來求。
            return kth ( rank ( val ) -  ) ;
        }

        inline int prov ( int val )  {
            return kth ( rank ( val +  ) ) ;
        }

        void display ( )  {
            display ( root ) ;
        }
} T ;

# undef N

//# define ZJC_LOCAL

int main ( )  {
# ifdef ZJC_LOCAL
    freopen ( "in.txt", "r", stdin ) ;
    freopen ( "out.txt", "w", stdout ) ;
# endif
    for ( register int M = In :: read ( ) ; M ; -- M )  {
        switch ( In :: read ( ) )  {
            case  :    T.insert ( In :: read ( ) ) ;  break ;
            case  :    T.erase ( In :: read ( ) ) ;  break ;
            case  :    Out :: print ( T.rank ( In :: read ( ) ) ), Out :: putc ( '\n' ) ;  break ;
            case  :    Out :: print ( T.kth ( In :: read ( ) ) ), Out :: putc ( '\n' ) ;  break ;
            case  :    Out :: print ( T.prev ( In :: read ( ) ) ),Out :: putc ( '\n' ) ;  break ;
            case  :    Out :: print ( T.prov ( In :: read ( ) ) ), Out :: putc ( '\n' ) ;  break ;
        }
    }
    Out :: flush ( ) ;
}