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