题目：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 ;
}
