首页 > 代码库 > BZOJ1858: [Scoi2010]序列操作

BZOJ1858: [Scoi2010]序列操作

这题我很二的折腾了一下午,唉,还是太弱了。这题的关键在于标记的更新与更新每个点的权值,更新标记我很快就写好了,思路很清晰,但是查找答案就头晕了,在处理下传标记、更新权值中纠结。。。。

这题我用sum来记录一段区间内1的个数,lest记录该区间从左往右连续的1的个数,rest记录该区间从右往左连续的1的个数,zest记录记录该区间中最长的连续1的长度。0同理用另一个数组记录。

下面考虑两个区间的合并,1的个数的合并很简单,直接将权值累加即可。最长连续的1的个数就有点麻烦了,一种情况就是直接从两个区间的zest的最大值继承过来,但这不一定是最优的,因为还有一种可能,就是左边区间的rest+右边区间的lest,这可能比之前的最大值更优。lest的值可以先从左边区间的lest继承过来,如果左边区间的lest=左边区间的总长度,说明当前区间的lest还能扩展到右边区间,那么只要左边区间的lest+右边区间的lest即可。处理rest反向考虑一下即可。

接下来考虑修改操作的合并,不难发现覆盖操作的优先级比取反高,因此如果当前操作是覆盖,直接覆盖之前的操作即可。如果是取反,那么也很好想,用1覆盖后在取反,不就是用0覆盖,用0覆盖后取反,就是用1覆盖,取反后再取反,就相当于没有取反~~lazy标记同理即可~是不是很简单

再接下来我们考虑对于每个记录我们该如何操作。也许你会问之前记录0是干嘛的,在这里就要发挥用处啦。如果当前是用1或0全部覆盖,那么把1或0的sum,lest,rest,zest全部赋为当前区间的长度即可。如果是取反,就是把0的信息给1,1的信息给0,直接交换0,1的sum,lest,rest,zest,是不是也很简单~~~~

之后就是坑爹的ADD和ASK了。。这个大家不同的线段树有不同的写法,我也不详说,注意一下下传标记和区间信息的更新。。还有就是求最长连续1的时候,左右合并要注意长度不能大于当前mid-l+1和r-mid。