# include <bits/stdc++.h>
const int N = 400000 + 5 ;
int ch [ N ] [ 2 ] ;
int ans [ N ] , siz [ N ] , same [ N ] , val [ N ] , fa [ N ] , buck [ N ] , c [ N ] , a [ N ] , pos [ N ] , inf = 1e9 + 7 ;
int n , x , tail , root , res , act , minx , sum ;
char s [ 15 ] ;
struct Splay {
void update ( int nd ) {
siz [ nd ] = siz [ ch [ nd ] [ 0 ] ] + siz [ ch [ nd ] [ 1 ] ] + same [ nd ] ;
}
void init ( ) {
root = 1 ;
ch [ 1 ] [ 1 ] = 2 ;
siz [ 1 ] = 2 ;
fa [ 2 ] = 1 ;
same [ 1 ] = same [ 2 ] = 1 ;
siz [ 2 ] = 1 ;
val [ 2 ] = inf ;
val [ 1 ] = - inf ;
tail = 2 ;
}
void rotate ( int nd , int pd ) {
int s = ch [ nd ] [ ! pd ] ;
int ss = ch [ s ] [ pd ] ;
int p = fa [ nd ] ;
fa [ nd ] = s ;
if ( p ) ch [ p ] [ nd == ch [ p ] [ 1 ] ] = s ;
else root = s ;
ch [ s ] [ pd ] = nd ;
ch [ nd ] [ ! pd ] = ss ;
if ( ss ) fa [ ss ] = nd ;
fa [ s ] = p ;
update ( nd ) ;
update ( s ) ;
}
void splay ( int nd , int top = 0 ) {
while ( fa [ nd ] != top ) {
int p = fa [ nd ] ;
int pp = fa [ p ] ;
int nl = nd == ch [ p ] [ 0 ] ;
if ( pp == top )
rotate ( p , nl ) ;
else {
int pl = p == ch [ pp ] [ 0 ] ;
if ( pl == nl ) {
rotate ( pp , pl ) ;
rotate ( p , nl ) ;
}
else {
rotate ( p , nl ) ;
rotate ( pp , pl ) ;
}
}
}
}
int find ( int nd , int vl ) {
while ( 1 ) {
if ( ! nd ) return - 1 ;
if ( val [ nd ] < vl ) nd = ch [ nd ] [ 1 ] ;
else if ( val [ nd ] > vl ) nd = ch [ nd ] [ 0 ] ;
else return nd ;
}
}
void Get_bef ( int nd , int vl , int & ans ) {
if ( ! nd ) return ;
if ( val [ nd ] > vl ) Get_bef ( ch [ nd ] [ 0 ] , vl , ans ) ;
else ans = nd , Get_bef ( ch [ nd ] [ 1 ] , vl , ans ) ;
}
void Get_aft ( int nd , int vl , int & ans ) {
if ( ! nd ) return ;
if ( val [ nd ] >= vl ) ans = nd , Get_aft ( ch [ nd ] [ 0 ] , vl , ans ) ;
else Get_aft ( ch [ nd ] [ 1 ] , vl , ans ) ;
}
void Insert ( int vl ) {
int tmp = find ( root , vl ) ;
if ( tmp != - 1 ) {
same [ tmp ] ++ ;
update ( tmp ) ;
splay ( tmp ) ;
return ;
}
int ans = 0 ;
Get_bef ( root , vl , ans ) ;
int lnd = ans ;
ans = 0 ;
Get_aft ( root , vl , ans ) ;
int rnd = ans ;
splay ( lnd ) ;
splay ( rnd , lnd ) ;
ch [ rnd ] [ 0 ] = ++ tail ;
same [ tail ] = 1 ;
val [ tail ] = vl ;
fa [ tail ] = rnd ;
update ( tail ) ;
update ( rnd ) ;
update ( lnd ) ;
// splay ( tail ) ;
}
void Delete ( int vl ) {
int ans = 0 ;
Get_aft ( root , vl , ans ) ;
int rnd = ans ;
splay ( 1 ) ;
splay ( rnd , 1 ) ;
fa [ ch [ rnd ] [ 0 ] ] = 0 ;
ch [ rnd ] [ 0 ] = 0 ;
update ( rnd ) ;
update ( 1 ) ;
}
void Add ( int vl ) {
res -= vl ;
act -= vl ;
}
void Sub ( int vl ) {
res += vl ;
act += vl ;
if ( res > minx )
Delete ( res ) ;
}
/*int Get_kth ( int nd , int k ) {
int rz = siz [ ch [ nd ] [ 1 ] ] ;
if ( rz >= k ) return Get_kth ( ch [ nd ] [ 1 ] , k ) ;
else if ( rz + same [ nd ] + 1 <= k ) return Get_kth ( ch [ nd ] [ 0 ] , k - rz - same [ nd ] ) ;
else return nd ;
}*/
int Get_kth ( int nd , int k ) {
int tmp = siz [ ch [ nd ] [ 0 ] ] + same [ nd ] ;
if ( siz [ ch [ nd ] [ 0 ] ] < k && k <= tmp ) return nd ;
return siz [ ch [ nd ] [ 0 ] ] >= k ? Get_kth ( ch [ nd ] [ 0 ] , k ) : Get_kth ( ch [ nd ] [ 1 ] , k - tmp ) ;
}
void debug ( int nd ) {
if ( ! nd ) return ;
debug ( ch [ nd ] [ 0 ] ) ;
if ( val [ nd ] != inf && val [ nd ] != - inf ) printf ( "%d " , val [ nd ] - act ) ;
debug ( ch [ nd ] [ 1 ] ) ;
} // 加入same值
}
Gyx ;
int main ( ) {
freopen ( "testdata.in" , "r" , stdin ) ;
freopen ( "testdatax.out" , "w" , stdout ) ;
scanf ( "%d%d" , & n , & res ) ;
minx = res ;
Gyx . init ( ) ;
for ( int i = 1 ; i <= n ; i ++ ) {
scanf ( "%s" , s ) ;
if ( s [ 0 ] == 'I' ) {
scanf ( "%d" , & x ) ;
Gyx . Insert ( x + act ) ;
if ( x + act >= res ) sum ++ ;
continue ;
}
if ( s [ 0 ] == 'A' ) {
scanf ( "%d" , & x ) ;
Gyx . Add ( x ) ;
continue ;
}
if ( s [ 0 ] == 'S' ) {
scanf ( "%d" , & x ) ;
Gyx . Sub ( x ) ;
continue ;
}
if ( s [ 0 ] == 'F' ) {
scanf ( "%d" , & x ) ;
Gyx . update ( ch [ root ] [ 0 ] ) , Gyx . update ( ch [ root ] [ 1 ] ) ;
Gyx . update ( root ) ;
int tmp , all = siz [ root ] - 2 ;
if ( all < x ) {
printf ( "-1\n" ) ;
}
else {
tmp = Gyx . Get_kth ( root , all - x + 2 ) ;
printf ( "%d\n" , val [ tmp ] - act ) ;
}
//kk ++ ;
}
//if ( kk == 11 || kk == 22 || kk == 40 ) printf ( "!!!!!!!!!!" ) ;
//printf ( "%s\n" , s ) ;
//printf ( "->" ) ;
//Gyx . debug ( root ) ;
//printf ( " siz :%d\n" , siz [ root ] - 2 ) ;
}
printf ( "%d" , sum - ( siz [ root ] - 2 ) ) ;
return 0 ;
}
by jerry119 @ 2018-09-13 11:33:44
请问解决了吗？我也90分wa第8个点啊
by ffacs @ 2019-07-31 13:37:03