<span>李超线段树复习笔记</span>
复习笔记就离谱好吧
用途
- 大概是给你一个序列， 然后插入一条线段， 然后查询某一个位置上与所有线段交点的纵坐标的的最大值或者最小值。
然后就没了。
实现
- 定义一个区间的"优势线段"为在这个区间里面有超过一半的点在这个线段上取到最值。
- 考虑维护一个线段树， 每个节点上保存了一条线段， 初始的时候没有保存， 表示这个区间的"优势线段"。
- 然后考虑怎么维护这个东西。下面均以维护最大值为例。
- 若当前区间还没有记录最优势线段，则记录最优势线段并返回。
- 若当前区间的最优势线段被插入的线段完全覆盖，也就是完全在被插入的线段下面， 则把最优势线段修改为被插入线段并返回。
- 若当前区间的最优势线段把被插入线断完全覆盖，则直接返回。
- 若当前区间最优势线段与被插入线段有交，则先判断哪条线段在当前区间更优，并把更劣的线段下传到交点所在子区间。因为有的线段虽然在这里不优， 但在小区间会更优。
- 可以到这里根据图片理解。
习题
- 最裸的板子。 [HEOI2013]Segment
- 最裸的板子。 [JSOI2008]Blue Mary开公司
- 恶心的板子。 [[SDOI2016]游戏]
- 优化dp。
不用写cdq了开不开心[CEOI2017]Building Bridges
Q:为啥你全给板子啊。
A:我确实只会做板子啊。
欢迎Dalao们加点题目， 救救孩子
