首先是这题
BZOJ3165: [Heoi2013]Segment
做法可以戳：wyl8899
实现的操作就是加入一条线段，然后询问与x=k相交的最大的y。（语文渣。。。）当然k和线段的左右端点的范围都是1--39989
做法就是维护一棵线段树，然后每个节点保存一条线段，这条线段完整覆盖整个节点所管辖的区间。
从一个叶节点到根节点共有O（logn）条线段。我们要确保叶节点的答案一定是由这O（logn）条线段得到的。
下面考虑如何维护这些线段。
以上纯属口胡。
总之先建一棵线段树。
我们考虑一个问题：这个问题为什么不能像普通的线段树的区间修改一样打lazy然后下传标记什么的呢？
因为标记不能快速合并。线段有可能相交，如果我们直接打标记的话，每个点的标记就不止一个，因为线段有相交问题。然后全部下传的话也和暴力是一个复杂度的。
那么考虑一下什么情况下标记是可合并的呢？
当然是一个区间内的两条线段不相交的时候。我们就可以直接抛弃下面的那条线段。
我们考虑采用标记永久化。
那么当一条线段到了一个节点与该节点的标记线段不相交的时候，我们直接取优的作为新的标记，然后返回。
否则我们可以判断这两条线段的交点在该节点的左子树还是右子树，不妨设为左子树，A线段在右子树的时候始终在B上方。
那么对于右子树来说一定不会选择B作为最优值，所以把A打在整个子树上，以后右子树的节点上来的时候直接用A更新ans。而B对左子树还是有贡献的。
所以在左子树我们递归插入B线段，这样不断递归下去。这样一次修改是O(log^2n）的。
所以查询的时候就往上爬然后用途径的所有线段更新ans即可。
感觉虽然说得不是很有理（因为这不是我想出来的解法
但似乎证明了这样做的正确性，以后写的时候心里也有底【捂脸熊】）
BZOJ1568: [JSOI2008]Blue Mary开公司
直接给根打标记。O（nlogn），读入坑死我。
BZOJ3938: Robot
我们把时间放在x轴，然后坐标放在y轴。那么每一个机器人其实可以分成若干条不相交的线段。可以预处理得到。
然后就和3165一样了。当然线段树得动态开点。但是空间复杂度不是O（nlog^2n）的？为什么到最后只用了200W+的点QAQ
然后又被坑死。。。我处理线段的时候分成了[l,r][r+1,rr]这样，然后发现同一时刻有可能对同一个机器人执行了两次操作。
那么我的线段就会出现[l,r][r+1,r]这样的线段。然后就爆掉了
一晚上没调出来居然是这个错
评论 (0)
