洛谷 P1486 & LOJ 10145 -「一本通 4.6 练习 2」郁闷的出纳员

题面

题目传送门

思路

看到题目的插入、删除和查询第 k 大操作,就想到了 Treap。

但是全部员工加减工资怎么办?仔细一看,这两种操作总条数不会超过 100,所以遍历整棵树更改数值就好了。

在增加工资的时候,一定不会有人离开。

在减少工资的时候,我们不断找工资底线 k 的前驱,如果它存在,就删除它。

最后的离开人数就是插入操作的次数减去最后的人数。

代码

暂无评论

发送评论


				
上一篇
下一篇