前言
大家好啊，今天讲的是 LCT (李超 Tree)(bushi
错了错了。这两不是一个东西。
概念
李超树能干什么。
- 插入一条直线/线段
- 单点查询当前点的峰值 (最大最小均可)
你会说：
OI 中有什么是和斜率相关的吗？
有，那就是斜率优化。
关于斜率优化可以看这个。
你会说：
你说的对，静态的 dp，CDQ 写的好常数小 \(n\log n\) 直接薄砂李超树。
所以李超树的优点就出来了：
- 好写好想，凸包啥的什么都不管。
- 是动态的
若是动态的，谁也不想写平衡树把……而且难维护。
所以，这就是 LCT！(李超树)(bushi
可是它的英文名就是 Li Chao Tree 啊。
前置芝士
- 初中的数学
- 动态开点线段树（因为有时候值域会飞天的大 有可能到 \(2^{60}\) 这个时候会不会平衡树维护凸包更好？)
模板：This （Upda:关于动态开点的数组大小问题，如果是单点修改的话请开 \(q\log w\)，区间的话建议能开多大开多开。如果实在卡， 理论上是 \(q\log w\)，常数是 \(2\)。不过这个有点玄学。 - 标记永久化
单点查询的优势就是这个。所以看到单点查询可以思考一下这个。
模板：This
算法思路
我们考虑标记永久化。
每次下标记。