算法刷题日记

本贴默认采用c++ 14，不过算法竞赛除了std以外用不到什么c++特性，大家自习翻译一下即可。

毒瘤线段树题，基本上囊括了所有线段树操作。对于区间子段问题我们考虑用pre,suf维护区间前缀后缀最值，pushup时考虑区间合并，若左区间全为1才能与后区间合并，新前缀为左区间长度+右区间前缀。后缀同理。统计答案时在左区间答案，右区间答案，左区间后缀+右区间前缀中取max。
具体维护，len：区间长，Max：最大连续长度，pre：最长1前缀，suf最长1后缀，pre_0：最长0前缀，suf_0：最长0后缀，sum：区间1数量，7种区间信息。
维护3种lazytag：tag：翻转。to_0：0覆盖。to_1：1覆盖。
在query时以结构体形式传递需要合并的两个区间信息，注意翻转标记下传需要取异或即可。思维难度不大，代码难写。

最近在复习数据结构，这周主要是线段树和平衡树。数据结构代码很抽象，不过都是板子，（自认为个人码风还是比较好看的）

顶

代码写的很好看。但是不要习惯用逗号分隔两个语句，如果你想表达函数内某两个语句是同一个小模块，就用空行把他们和前面分隔开，这是更常用的规范表达。

二分+线段树。最后询问考虑离线，暴力对子序排序显然nlogn，mnlogn不能忍受。（通过题目标签）我们可以自然想到线段树做法。线段树非常适合做01合并因为询问仅存在于修改后单点，考虑二分答案，序列中>=mid的设为1否则为0，排序只需要查询区间1个数，然后按1个数0个数正序/逆序推平区间即可，若q位置为>=1，说明区间修改后该位置结果>=ans，令val=mid+1继续二分否则说明猜测值过大val=mid-1。这题更优秀的在线线段树分裂+平衡树，但是太难了，就不写了（

厉害

昨天有事，今天继续更

一道送分的NOI题，一开始想的是整体维护，维护覆盖某个点的最长和最短区间，但是发现转移几乎不可能。考虑到本题不需要考虑具体哪个点做出的贡献，于是维护整体最大覆盖点，将区间按长度排序后，如果发现某个点被覆盖m次，说明已经合法。对于最小范围考虑双指针优化，发现点被覆盖m次后统计答案，删除最早加入的区间，直到覆盖不足m次，加入下一个区间，过程用线段树维护。

扫描线，线段树比较重要的一个运用，虽然考的比较少，今天动手打码一个。原理不在贴吧细讲了，有兴趣可以去我blog看。讲几个细节，首先线段树维护的是点贡献叠加，我们不能按常理的线段[l,r]加入线段树，因为有可能[1,3]被拆成[1,2]和[3]，[2,3]的贡献就寄了，于是我们定义线段树叶子l表示第l根线段到第l-1根线段的距离，线段加入线段树做左区间偏移即可。

注意update函数清空覆盖标记不是设置区间贡献是0！而是让两个子区间上传，这个地方debug了好久。