总结了一些槽点。
查看原帖
总结了一些槽点。
375208
LawrenceSivan楼主2021/7/24 16:40

发现这个题坑点是真的多,于是搜寻了部分错误,希望帮到大家

细节(槽点)

  1. 玩的就是区间树嘛,基本操作转转转!哨兵节点不要忘记加入。就算加入了哨兵节点也别放松,你后面找到对应位置的时候都得 +1+1
  2. a[1],a[n+2]a[1],a[n+2] 的值要置成 INF-INF ,否则会影响最大字段和
  3. 本题要一大段一大段地添加数字,你可别像个傻子一样一个一个往里面插值,那样就 O(nlogn)\mathcal{O(n\log n)} 了。搞个建树,像线段树一样就好了,复杂度 O(n)O(n) ,之后直接把这个新树的根节点拉到 Splay 上去就行了。
  4. 本题节点是有负数的!一开始 00 号节点的最大子段和一定要赋值成 -INF
  5. 建树完了不要忘记 push_up
  6. 空间问题:可以发现他树中最多 5e55e5 个数,但是他可能要添加多达 4e64e6 个数!浪费的节点不要扔掉,写一个垃圾桶循环利用!
  7. 更改操作不要全都删除然后再重新插入,用个更改标记就好了。更改标记一开始最好置一个极大或者极小值,不够极端都有可能导致出现问题,千万不要直接赋值成 00 !,他是有可能把一整个区间都变成 00 的!
  8. 关于求最大子段和:这和线段树那个其实略有差别,但是差别不大。需要注意的是,线段树只有两个区间,直接合并就可以了。而这道题一个节点除了两个子节点,还有他自己需要考虑。所以有些位置需要加上自己的贡献
  9. 本题子段 不可以 选空段! 就是说即使你的区间里全是负的,你至少也要选择一个。新建节点直接让最大子段等于当前位置。虽然最大子段不能是空段,但是你的左右子段还是可以是空段的,毕竟就算所有都是空段,加上自身位置,就不是空段了(自身位置由于开始赋值所以必定不是空段)
  10. 下传标记之前一定要看看到底有没有这个节点!比如这道题的 #33 ,#77,他会对一个空段进行操作。如果你是指针党,你就直接 RE 了。
  11. 反转了区间你的左右子段要互换位置
  12. 下传标记一定要先传修改再传翻转。(其实也不必要,只是这样做的话结合下一点可以减少一些常数)
  13. Splay 常数比较大,如果你需要卡常,有一个小技巧:当你进行完区间修改操作之后,可以发现你的区间都是一样的了,所以左右反转操作就没用了。所以下传完修改标记之后可以直接把翻转标记置 00 ,(也有可能快不了多少,但是如果你到了绝境就可以试试)
  14. 关于修改区间的问题(如果你脑子还比较清醒的话就可以不用看这一条)首先加了哨兵节点,你的所有位置都是平移一得。例如:pospos+1pos\rightarrow pos+1pos+len1(pos+len1)+1pos+len-1\rightarrow (pos+len-1)+1于是你要反转一个区间的时候,你需要找到 l1,r+1l-1,r+1 这两个位置。l1=(pos+1)1l-1=(pos+1)-1r+1=((pos+len1)+1)+1r+1=((pos+len-1)+1)+1,于是就变成了 pospospos+len+1pos+len+1
  15. 改变了父子关系或者是儿子情况出现了变化一定要记得 push_up
  16. 标记多传几次是没有关系的,如果你害怕没传下去就多传几次
  17. 寻找 kth 时要下传标记(这个上面貌似说过了)
  18. 回收一定要在把它的父节点的左儿子清空之前,要不然你清空了再回首就找不到那个地方了。

总结

也许还有什么我不知道的点,但是大部分错误都能在上面找得到了。

写数据结构题就是要保持一颗健康不病态,积极向上的心态。

还有一个功能强大的肝

祝大家成功!

2021/7/24 16:40
加载中...