4
21
2015
0

一类和线段树&&凸包有关的问题

首先是这题

 

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]这样的线段。然后就爆掉了一晚上没调出来居然是这个错

Category: 专题 | Tags: | Read Count: 623

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com