关于此题的一个疑问
查看原帖
关于此题的一个疑问
93701
Morgen_Kornblume楼主2021/10/3 12:34

我用 Splay A 了这个题,但是我还是有一些疑问:

这道题如果用 Splay 操作 + 下传懒标记 处理减少工资后踢人的情况的话(找到第一个不会被踢掉的人,把他转到根,然后砍掉他的左子树,被踢掉的就是左子树上的所有人<因为由 BST 性质知,他们的工资都小于下界>),

那么每一次这样的处理应该都是 log(n) 的,但是题目中的添加工资和减少工资的操作数总和却不超过 100 ,数据的值域还比较局限,尤其是没有强制在线,很多其他的方法(线段树之类)应该就是利用了这一点暴力操过去的。

所以,我想请大佬给这道题出一个加强版(开大值域,强制在线,操作不限)来只放 Splay 之类的过去。

2021/10/3 12:34
加载中...