傳送門
題目看起來玄乎,但其實只需要一點點小 trick 就可以了.

我們可以用一個全局的 delta 來維護工資的調(diào)整記錄

對于每一個新加入的員工,先判斷是否低于最低工資下限,如果是,直接踢出,不做任何操作,否則,將其插入 Treap 中,不過這時為了不對以后的查詢產(chǎn)生影響,我們要插入的值時 key-delta (想一想,為什么?)

對于加工資的操作,直接在 delta 上統(tǒng)計即可.而減工資,這可能牽扯到會有員工離開,所以我們不能只修改delta

我們在修改 delta 之后,把 Treap 按權(quán)值分割,分割標準是 minn-delta-1 (想一想,為什么?提示:不等式移項)

然后直接舍棄整個的左子樹,此時的左子樹就是所有會離開公司的員工代表的節(jié)點,所以最后的答案要加上該子樹的 size

對于查詢操作,直接查詢出來的第 k 小(注意!!!是第 k 小)加上 delta 即可

Code:

#include <iostream> #include <cstdlib> #include <cstdio> #include <ctime> #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 ; }

轉(zhuǎn)載于:https://www.cnblogs.com/Equinox-Flower/p/10785300.html

總結(jié)

以上是生活随笔為你收集整理的NOI2004郁闷的出纳员的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。