BZOJ-3117: [Noi1999]内存分配（平衡树）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3117

用一个优先队列来处理时间的关系，然后一个队列存等待队列的东西，内存部分用一棵平衡树维护，这样就可以O(q log q)了。

代码（splay）：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

   

using namespace std ;

   

const int maxv = 10100 ;

   

struct node {

        node *lc , *rc , *fa ;

        int l , r , maxl , len ;

        inline void update(  ) {

                maxl = max( max( lc -> maxl , rc -> maxl ) , len ) ;

        }

} bst[ maxv ] ;

   

node *root , *pt = bst , *null ;

   

int n ;

   

inline void Init_splay(  ) {

        null = pt ++ ;

        null -> lc = null -> rc = null -> fa = null , null -> len = null -> maxl = 0 ;

        node *l = pt ++ , *r = pt ++ ;

        l -> lc = l -> fa = r -> lc = r -> rc = null ;

        l -> l = -1 , l -> r = -1 , r -> l = n , r -> r = n , r -> len = 0 , l -> len = n ;

        ( l -> rc = r ) -> fa = l ;

        ( root = l ) -> update(  ) ;

}

   

#define C( t ) ( t == t -> fa -> lc )

   

inline void zag( node *t ) {

        node *k = t -> rc , *u = t -> fa ; bool flag = C( t ) ;

        ( ( t -> rc = k -> lc ) -> fa = t ) -> update(  ) ;

        ( ( k -> lc = t ) -> fa = k ) -> update(  ) ;

        if ( ( k -> fa = u ) != null ) if ( flag ) u -> lc = k ; else u -> rc = k ;

}

   

inline void zig( node *t ) {

        node *k = t -> lc , *u = t -> fa ; bool flag = C( t ) ;

        ( ( t -> lc = k -> rc ) -> fa = t ) -> update(  ) ;

        ( ( k -> rc = t ) -> fa = k ) -> update(  ) ;

        if ( ( k -> fa = u ) != null ) if ( flag ) u -> lc = k ; else u -> rc = k ;

}

   

inline void splay( node *t , node *v ) {

        while ( t -> fa != v ) {

                if ( t -> fa -> fa == v ) if ( C( t ) ) zig( t -> fa ) ; else zag( t -> fa ) ; else {

                        if ( C( t ) ) {

                                if ( C( t -> fa ) ) zig( t -> fa -> fa ) ; zig( t -> fa ) ;

                        } else {

                                if ( ! C( t -> fa ) ) zag( t -> fa -> fa ) ; zag( t -> fa ) ;

                        }

                }

        }

        if ( v == null ) root = t ;

}

   

inline node* select( int L ) {

        if ( root -> maxl < L ) return null ;

        node *t = root ;

        while ( 1 ) {

                if ( t -> lc -> maxl >= L ) t = t -> lc ; else

                if ( t -> len >= L ) break ; else t = t -> rc ;

        }

        splay( t , null ) ;

        return t ;

}

   

struct ntype {

        node *t ;

        int T ;

        ntype( node *_t , int _T ) : t( _t ) , T( _T ) {

        }

        bool operator < ( const ntype &a ) const {

                return T > a.T ;

        }

} ;

priority_queue < ntype > pq ;

   

inline bool add( int s , int len , int P ) {

        node *pre = select( len ) ;

        if ( pre == null ) return false ;

        node *suff = pre -> rc ;

        for ( ; suff -> lc != null ; suff = suff -> lc ) ;

        splay( suff , pre ) ;

        node *t = pt ++ ;

        t -> lc = t -> rc = null , ( suff -> lc = t ) -> fa = suff ;

        t -> l = pre -> r + 1 , t -> r = pre -> r + len ;

        t -> len = t -> maxl = suff -> l - t -> r - 1 , pre -> len = 0 ;

        suff -> update(  ) ; pre -> update(  ) ;

        pq.push( ntype( t , s + P ) ) ;

        return true ;

}

   

inline void del( node *t ) {

        splay( t , null ) ;

        node *pre = t -> lc , *suff = t -> rc ;

        for ( ; pre -> rc != null ; pre = pre -> rc ) ;

        for ( ; suff -> lc != null ; suff = suff -> lc ) ;

        splay( pre , t ) , splay( suff , t ) ;

        pre -> len = suff -> l - pre -> r - 1 , pre -> fa = null ;

        ( ( pre -> rc = suff ) -> fa = pre ) -> update(  ) ;

        root = pre ;

}

   

queue < pair< int , int > > q ;

   

int cnt = 0 ;

   

int main(  ) {

        scanf( "%d" , &n ) ;

        Init_splay(  ) ;

        int T , M , P , Time = 0 ;

        while ( 1 ) {

                scanf( "%d%d%d" , &T , &M , &P ) ;

                if ( T == 0 && M == 0 && P == 0 ) break ;

                while ( ! pq.empty(  ) ) {

                        ntype now = pq.top(  ) ;

                        if ( now.T > T ) break ;

                        Time = now.T;

                        while ( ! pq.empty(  ) ) {

                                now = pq.top(  ) ;

                                if ( now.T == Time ) {

                                        del( now.t ) ;

                                        pq.pop(  ) ;

                                } else break ;

                        }

                        pair < int , int > p ;

                        while ( ! q.empty(  ) ) {

                                p = q.front(  ) ;

                                if ( ! add( Time , p.first , p.second ) ) break ;

                                q.pop(  ) ;

                        }

                }

                Time = T ;

                if ( ! add( T , M , P ) ) {

                        ++ cnt , q.push( make_pair( M , P ) ) ;

                }

        }

        while ( ! pq.empty(  ) ) {

                ntype now = pq.top(  ) ;

                Time = now.T ;

                while ( ! pq.empty(  ) ) {

                        now = pq.top(  ) ;

                        if ( now.T == Time ) {

                                del( now.t ) ;

                                pq.pop(  ) ;

                        } else break ;

                }

                pair < int , int > p ;

                while ( ! q.empty(  ) ) {

                        p = q.front(  ) ;

                        if ( ! add( Time , p.first , p.second ) ) break ;

                        q.pop(  ) ;

                }

        }

        printf( "%d\n%d\n" , Time , cnt ) ;

        return 0 ;

}