我们可以用一个全局的 delta 来维护工资的调整记录
对于每一个新加入的员工,先判断是否低于最低工资下限,如果是,直接踢出,不做任何操作,否则,将其插入 Treap 中,不过这时为了不对以后的查询产生影响,我们要插入的值时 key-delta (想一想,为什么?)
对于加工资的操作,直接在 delta 上统计即可.而减工资,这可能牵扯到会有员工离开,所以我们不能只修改delta
我们在修改 delta 之后,把 Treap 按权值分割,分割标准是 minn-delta-1 (想一想,为什么?提示:不等式移项)
然后直接舍弃整个的左子树,此时的左子树就是所有会离开公司的员工代表的节点,所以最后的答案要加上该子树的 size
对于查询操作,直接查询出来的第 k 小(注意!!!是第 k 小)加上 delta 即可
Code:
#include#include #include #include #define Drt pair < Treap * , Treap * >#define siz(rt) ( rt == NULL ? 0 : rt->size )#define int long longusing std :: pair ;int n , minn , cnt , delta ;struct Treap { Treap * son[2] ; int val , size , rank ; Treap (int val) : val ( val ) { size = 1 ; son[0] = son[1] = NULL ; rank = rand () ; } inline void maintain () { this->size = 1 ; if ( this->son[0] != NULL ) this->size += this->son[0]->size ; if ( this->son[1] != NULL ) this->size += this->son[1]->size ; return ; }} * root = NULL ;inline Drt Split ( Treap * rt , int k ) { if ( rt == NULL ) return Drt ( NULL , NULL ) ; Drt t ; if ( k <= siz ( rt->son[0] ) ) { t = Split ( rt->son[0] , k ) ; rt->son[0] = t.second ; rt->maintain () ; t.second = rt ; } else { t = Split ( rt->son[1] , k - siz ( rt->son[0] ) - 1 ) ; rt->son[1] = t.first ; rt->maintain () ; t.first = rt ; } return t ;}inline Drt SplitV ( Treap * rt , int key ) { if ( rt == NULL ) return Drt ( NULL , NULL ) ; Drt t ; if ( rt->val <= key ) { t = SplitV ( rt->son[1] , key ) ; rt->son[1] = t.first ; rt->maintain () ; t.first = rt ; } else { t = SplitV ( rt->son[0] , key ) ; rt->son[0] = t.second ; rt->maintain () ; t.second = rt ; } return t ;}inline Treap * merge ( Treap * x , Treap * y ) { if ( x == NULL ) return y ; if ( y == NULL ) return x ; if ( x->rank < y->rank ) { x->son[1] = merge ( x->son[1] , y ) ; x->maintain () ; return x ; } else { y->son[0] = merge ( x , y->son[0] ) ; y->maintain () ; return y ; }}inline int Getrank ( Treap * rt , int key ) { if ( rt == NULL ) return 0 ; if ( key <= rt->val ) return Getrank ( rt->son[0] , key ) ; else return Getrank ( rt->son[1] , key ) + siz ( rt->son[0] ) + 1 ;}inline int Getkth ( Treap * & rt , int key ) { Drt x = Split ( rt , key - 1 ) ; Drt y = Split ( x.second , 1 ) ; Treap * node = y.first ; rt = merge ( x.first , merge ( node , y.second ) ) ; return node == NULL ? 0 : node->val ;}inline void insert ( Treap * & rt , int key ) { int k = Getrank ( rt , key ) ; Drt t = Split ( rt , k ) ; Treap * node = new Treap ( key ) ; rt = merge ( t.first , merge ( node , t.second ) ) ; return ; }signed main () { scanf ("%lld%lld" , & n , & minn ) ; while ( n -- ) { char opt[4] ; int key ; scanf ("%s%lld" , opt , & key ) ; if ( opt[0] == 'I') { if ( key < minn ) continue ; insert ( root , key - delta ) ; } if ( opt[0] == 'A') delta += key ; if ( opt[0] == 'S') { delta -= key ; Drt t = SplitV ( root , minn - delta - 1 ) ; root = t.second ; cnt += siz ( t.first ) ; } if ( opt[0] == 'F') { if ( key > siz ( root ) ) printf ("-1\n") ; else printf ("%lld\n" , Getkth ( root , siz ( root ) - key + 1 ) + delta ) ; } } printf ("%lld\n" , cnt ) ; system ("pause") ; return 0 ;}