描述
要求支持区间插入、区间修改、区间翻转、区间删除、区间求和 和求和最大的子列.
分析
- 从最开始学完splay做了翻转区间后就想做这个题目, 结果WA了N次后失去调试的信心, 40分收场(这题暴力30分)
- 快省选了想拿出来再做一下, 因为splay的区间操作这个题算是最全的了, 不做一下的话总担心模版是错的.
- 然后做了好长时间...终于不耐烦了拿HZWER的改了改, 直到改到所有操作和我的都写的一模一样——除了标记下传. 然后就很开(伤)心地接受了这个现实.
- 在网上看每个人写的标记下传都不一样, 有的写的简单有的很复杂(比如HZWER). 但一种标记下传对应一种维护方式吧, 看网上很少有写如何处理细节的, 我就写详细点吧.
- 首先, mls, mrs, maxs分别记录左、右端开始的最大子序列和, 和整段区间的最大子序列和.
- 规定如果整段区间为负值, mls和mrs可以取0, 而maxs必须取一个存在的数, 这样也是为了维护起来方便吧.
- 那么mls可以取左子结点的mls、左子结点的sum+根结点的权值+右子结点的mls. mrs同理.
- maxs可以取左子结点的maxs、右子结点的maxs、左子结点的mrs+根结点权值+右子结点的mls.
- 这就是mls、mrs最小为0的优势.
- 在标记下传时下传的实际上是子结点的标记, 而根结点的标记实际上已经在此之前生效了. 这样可以避免在旋转时来不及调整标记而出错.
- 遇到带区间修改的题目都要用这种标记下传的方式吧..
CODEVS-1758-维护数列-NOI2005-splay
原文：http://blog.csdn.net/qq_21110267/article/details/44873991
