Problem’s Website
Solution
这道题是平衡树的一道模板题,可以用Treap做,但是我太菜了,于是我用fhq−Treap做。
这道题加深了我对fhq−Treap分裂操作的理解。
首先,我们再处理A和S命令时不需要全部加或减,我们用一个变量当做标记,在处理I命令时把新的k减去标记即可。
其次,关于如何处理员工因工资太低而离开公司的问题
1.在插入时,我们最低值-标记-1进行分裂,也就是说,分裂后左边的树,就是要离开公司的内容,我们只需要让root=y,就说明我们把左边的树去掉了。
2.在集体减工资时,我们也进行同样的操作,同时,我们可以维护离开公司的人数,让ans加上siz[x]即可。
最后,关于输出第k多工资的问题
我们要判断这个第k多工资的员工是否离开了公司,如果k≤siz[rt]就说明该员工没有离开公司,可以输出,否则就输出−1,感觉这个还是很好理解的。
Code
1 |
|
rp++
Gitalking ...