能直接使用常规的单调队列或者单调栈写法。
具体做法可见我之前写的 斜率优化学习笔记。
这里详细讲一下二进制分组的做法。
做法
感觉网上说的理解都比较神秘，实际上很好理解。
其实这玩意和线段树是一个类似逻辑，我们相当于第 �i 次修改是在线段树上的 �i 位置加上一个值。
如果这个点还有一个兄弟节点，那么就可以通过其父亲进行查询。
那么我们就把这个点和其兄弟合并，置于其父亲节点。
其父亲再看能不能和兄弟合并，以此循环下去，直到没有兄弟。
这样每个点都只合并了树高次，是log�logn的，时间复杂度的优势就体现在这。
实际做的时候显然不需要模拟线段树，只需要记录每个区间大小，再不断合并即可。
那么维护凸包同理。
我们每次加入一个大小为 11 的凸包，看看之前有没有大小和它一样的。有，就不断合并，直到没有。
每次合并，对凸包进行重构，凸包有�(�log�)O(klogk)的单次处理方法，因此构造的总的时间复杂度就是�(�log2�)O(nlog2n)的。
查询显然只需要每一组求一个最值，再在这些最值里面取出最值即可，总的时间复杂度仍然是�(�log2�)O(nlog2n)的，因为每次查询需要在一个块内二分一次。
让我看看
删除操作
二进制分组处理删除通常有两种情况：
1. 可差分的信息
如果维护的值满足可加减性（例如求和、计数），可以维护两个二进制分组结构：一个存放增加的贡献，另一个存放删除的贡献。查询时用“增加的答案”减去“删除的答案”即可。这种方法实现简单，且时间复杂度不变。
2. 不可差分的最值信息删除最后一个值
对于最大值、最小值等不可差分的信息，减法不再适用。如果只需要支持删除最后一次加入的元素（即栈式删除），可以考虑进行魔改：
- 将每一层的容量限制从“最多一个组”放宽为“最多两个组”。
- 当某一层出现三个大小相同的组时，才将前两个组合并成一个两倍大小的组，第三个组继续保留。
- 删除元素时，直接从最后加入的组中移除对应元素。
该方法保持了插入均摊�(�log2�)O(nlog2n)，整体仍为�(�log2�)O(nlog2n)。
3. 不可差分的最值信息删除任意值
如果需要删除任意位置（而非仅末尾）的元素，处理方式取决于内层数据结构是否支持删除。
对于 KDT 等可以打标记的结构：
- 删除时，先在各个组内查询到要删除的元素（�(log�)O(logn)的时间），然后打上删除标记。
- 查询时，遍历组的过程中跳过被标记的元素。
- 为了防止标记点堆积过多，维护一个全局计数器：当被标记删除的元素总数超过当前未删除元素数的一半时，触发一次全局重构，将所有未删除的元素重新分组。
- 全局重构的代价是�(�log�)O(nlogn)（假设内层结构重建是 �(�log�)O(klogk) 的），均摊到每次删除上是�(log�)O(logn)。
对于凸包等不能打标记的结构：
- 凸包查询依赖二分和几何结构，打标记会破坏这一前提——二分命中的点可能是已删除点，而简单地“跳过它取相邻点”不能保证答案正确。
- 因此，凸包通常不支持打标记删除任意元素。如果确实需要支持删除，一般有两种选择：
- 改用支持动态删除的凸包结构（如平衡树维护凸壳），放弃二进制分组的轻量优势。
- 如果删除操作不多，可以在每次删除后直接对该组暴力重构（即删除后立即重建该组的凸包）。单次代价为�(�log�)O(klogk)（�k 为该组大小），若删除次数较少则整体可接受。
