BZOJ原题地址

洛谷原题地址

思路

可以用线段树很方便地维护,对于每个区间,如果要加地线段在中点处更优,就替换原有的线段。

对于每条新加入的线段,我们需要用$log(n)$ 的复杂度将它分配到不同的区间内,对于每个区间,又要用$log(n)$的复杂度判断在所有子区间的优劣程度。

所以,插入复杂度是$log^2(n)$的,查询复杂度依然为$log(n)$。

代码实现

使用结构体$Node$存储每条线段的信息。

对于一条编号为$id$的线段,它的左端点是$(l,yl)$,而右端点是$(r,yr)$。判断交点的存在性和位置时,我们使用$Node.k$来获取这条线段的斜率。

在插入时,我们会不断调整新线段的左右端点位置以确保被当前区间覆盖,使用$Node.lm()$ / $Node.rm()$ 实现这个操作。

对于斜率不存在的线段要简单地特殊处理一下,我的插入方法能规避很多特判。

细节见注释。

  1. 【正睿 OI 】2018 提高组十连测 Day 2 / 题解 – XG Zepto's
    Sep 03, 2018

    […] 为了避免开两棵线段树,可以把二三两个象限的线段沿 $x$ 轴翻转,然后就是 Segment 原题了。 […]

    Reply