本文介绍了笔者由一道题的根号做法受到启发，独自摸索出来的一个数据结构。
由于笔者能力和精力有限，无法查找已有的资料，如果有哪位巨已经提出来了记得踩我一脚。
介绍
这个数据结构维护凸包，支持以下操作：
- \(O(\sqrt{n})\) 在线加入/删除任意一条线段
- \(O(\sqrt{n}\log\sqrt{n})\) 在线询问/\(O(\sqrt{n})\) 离线询问当 \(x=i\) 时 \(y\) 值最大/最小的线段
- \(O(\sqrt{n})\) 在线合并两个凸包
实现方式
设总线段数为 \(n\)，每个凸包内将所有线段分块，按照 \(\sqrt{n}\) 条线段为一块，块内线段由斜率从小到大排序。整个凸包由若干大小为 \(\sqrt{n}\) 的块（后称“整块”）和最多一个大小不足 \(\sqrt{n}\) 的块（后称“散块”）组成。
每个整块中预处理出一个凸包，该凸包的拐点数不超过 \(\sqrt{n}\)。组成凸包的所有线段将值域切割为不超过 \(\sqrt{n}\) 段。
加线段时，直接往散块中暴力插入保持斜率从小到大排序，若散块的大小大于 \(\sqrt{n}\) 则把它变成整块，新建一个空的散块。
删线段时，如果该线段处于散块中则可以暴力删除；如果该线段处于整块中则破坏整块，将整块中的线段与散块中的线段进行二路归并，保持斜率从大到小排序。若散块的大小大于 \(\sqrt{n}\)，从中提取出任意 \(\sqrt{n}\) 个元素作为一个单独的整块。
查询时遍历所有整块，二分查找，对散块的所有元素暴力即可。离线打懒标记可以做到不带 \(\log\)。
在线合并考虑合并整块，合并散块，若散块的大小大于 \(\sqrt{n}\)，从中提取出任意 \(\sqrt{n}\) 个元素作为一个单独的整块。