好久没发这种“告诫后人”的帖子了,上一次发还被 zhoukangyang 喷了,所以这一次想要造福社会于是就给那些调不出来的 Splay 玩家一个提示(
1. 插入之后要 Splay 上去
Splay 除了旋转,它还能更新信息。插入 x 之后它的所有祖先的信息都要更新,你难道敢不 Splay 吗?其实,如果你不 Splay,它不仅会 WA,甚至在特殊构造的数据下还会 TLE。
2. 一个节点有多个副本
我们要用一个数组来维护各个节点的副本数量。也许你已经想到了这点?但你可能在代码中的某些地方下意识地写成了 1,请仔细检查。
3. 下传标记与上传标记
你在 Rotate 函数里面下传、上传标记了吗?
Pushdown 要在三次 connect 之前(如果题目需要的话)。
Pushup 要在三次 connect 之后(如果题目需要的话)。
4. 如果当前插入的这个人已经小于了工资下界
你就不能插入这个人。
5. 如果所有人都被劝退了呢?
请仔细思考这个问题,并在你的代码中检查是否会在此情况下出现错误。常见体现是 WA #3.