动态凸包 - having little or no sense, use, or purpose.

这里提供用另外一个角度去提出动态凸包的算法，就可能不需要写可持久化平衡树了…

二维凸包

凸包：上凸壳下凸壳（之后只考虑上凸壳）

维护点集$S$的上凸壳

可能需要支持的操作：

修改类：加入、删除一个点

询问类：整体/区间询问凸包上的边/某个方向最远点

考虑支持求出凸包

修改操作的性质：

离线/在线

只有加/只有删/又有加又有删

加的点坐标单调/不单调

可持久化（回到历史版本）/不可持久化

离线只有删 <=> 离线只有加

在线 => 离线

几种凸包算法

Graham 要求加点坐标单调。

将凸壳上的点顺序存于数组中

支持在线加点，单次复杂度O(delta凸壳点数)，总复杂度$O(n)$

魔改版Graham，支持可持久化。要求加点坐标单调

因为每次加点是删后缀，所以可以将凸壳的点存在树上，一个版本就是树上的一条路径。

每次加点删点就相当于把一个树的后缀删掉，相当于在树上二分。

二分在线加点，单次O(log 当前凸壳点数)，总复杂度$O(n\log n)$。

平衡树版 Graham(?) 不要求加点坐标单调

将凸壳上的点按照某一维坐标为关键字，排在平衡树上

在线加点，暴力删除周围点

如果使用std::set(finger search)。

finger search指对于一棵平衡树，比如set有一个操作为it++或者it--，这实现了一个找前驱后继的过程。找前驱后继时先往上找，然后再往下找。遍历一个大小为$O(sz)$的集合的时间复杂度是$O(sz+\log)$。用这个来实现找前驱后继的，那么遍历一棵平衡树的时间复杂度是$O(n+\log)$的，即$O(n)$级别的。即单次做it++操作最坏复杂度是$O(\log)$的，但是做$sz$遍的时间复杂度是$O(sz+\log)$。

所以单次复杂度O(delta凸壳点数+log(凸壳点数))，总复杂度$O(n\log n)$，不可持久化。

如果手写平衡树，$O(1)$删除子树（修改指针），则单次复杂度O(log(凸壳点数))，可持久化。

完全动态凸包

在线不要求单调可加可删可持久化

两类实现方法：

类线段树实现
可持久化平衡树 cls论文《可持久化数据结构研究》

可持久化平衡树

只是可以回到历史状态的平衡树而已

可持久化的本质：记录所有时刻的历史版本，“垃圾不回收”

维护的所有版本原则上不可修改，修改应视为新的版本

适用于指针维护的数据结构，可持久化代价为一个点所连接的指针数

理论上非均摊复杂度的平衡树都可以持久化，但是非旋treap比较好写

可持久化平衡树版完全动态凸包

对于两个$x$轴上不相交的上凸壳，合并后为前缀+一条边+后缀，大概长这个样子：

为快速合并凸壳且保持结构完整，我们可以用可持久化平衡树维护按照$x$坐标排序的凸壳点集

外层使用平衡树等结构动态维护整个点集，树中每个点维护一个可持久化平衡树表示子树内点集凸壳即可。

类线段树实现

线段树结构，叶子节点维护一个单独的点，非叶子节点维护子树（区间）内点集凸壳信息

要求左子树的点集的坐标严格小于右子树的点集的坐标（相当于将所有点按坐标排序后建线段树）

假设我们已经求出了左右子树的凸壳，那么合并后的凸壳一定是左子树的凸壳的一段前缀+一条边+右子树凸壳的一段后缀

核心思想：每个节点只维护这条跨左右子树的边

记号：

节点$x$维护的边记作$bridge(x)=(p(x),q(x))$

叶子节点维护的点记作$a(x)$

对于叶子节点，我们令$bridge(x)=(a(x),a(x))$

注意我们的结构并没有直接地表示出凸壳

对于节点$x$，考虑它子树点集的凸壳，将凸壳上的点称为关键点，更小的凸壳上一定会出现这些关键点

设这些关键点对应的叶子节点集合为$S$，设$T$为$S$形成的虚树

$T$有$|S|$个叶子节点，$|S|-1$个非叶子节点，这其实就对应这$|S|-1$个横跨边，而这$|S|-1$个非叶子节点维护的边按照中序排列即为$x$的子树的凸壳

如何判断哪些节点在虚树上？（哪些边是凸壳的边？）

考虑暴力过程：先求出左右子树的凸壳，再删除被$bridge(x)$包含的边（包含指坐标区间包含）

等价于：从$x$开始dfs，每次只加入没有被祖先的$bridge$包含的边

判断$bridge(u)$是否在$x$节点子树的凸壳上的条件：对于所有$fa(u)$到$x$的路径上的$v$，$bridge(u)$不被$bridge(v)$包含

时间复杂度与虚树时间复杂度一样，$O(md)$，$m$为凸壳上子树个数，$d$为子树深度。

因为只用判与这个区间有交的横跨边，否则再左或再右就没有必要去管。

如何计算$bridge$：（合并左右子树的凸壳）

考虑$bridge(x)$连接了左子树的$p(x)$和右子树的$q(x)$

所有$p(x)$左方的边向右延长的射线在右子树凸壳的上方，同理$q(x)$右方的边向左延长的射线在左子树凸壳的上方

考虑二分出$p(x)$和$q(x)$

单独二分一边时需要另一边求某个方向的最远点，再次二分的话需要两个$\log$

考虑一起在树上二分，假设我们确定$p(x)$在$u$的子树内，$q(x)$在$v$子树内

若$bridge(v)$中的某一点在$bridge(u)$射线上方，那么$p(x)$一定在$u$的左子树内

同理，若$bridge(u)$中的某一点在$bridge(v)$射线上方，那么$q(x)$一定在$v$的内

如果出现这两种情况，我们就可以缩小范围。

如果两个情况都不满足，我们考虑$bridge(u)$和$bridge(v)$射线的交点。

假设交点的坐标不在$u$子树的坐标范围内，那么$q(x)$一定在$v$的左子树内。同理如果不在$v$子树的坐标范围内，那么$p(x)$一定在$u$的右子树内。

$u$和$v$的坐标范围不交，所以以上两种情况至少会发生一种。

计算$bridge(x)$的复杂度O(x子树的深度)。

我们数据结构里节点需要维护的信息有：$bridge(x)$，$x$子树的坐标范围

其中$bridge$的计算复杂度依赖于深度，坐标范围可以$O(1)$直接合并

对于离线（预先知道用到的点坐标），可以使用线段树

对于在线，可以用非均摊的平衡树（如treap）

单点修改（包括删点、加点）只会影响到到根的路径上的节点，复杂度严格$O(\log^2 n)$

区间询问凸包需要合并$O(\log n)$，复杂度严格$O(\log ^2 n)$

对于用这个数据结构表示的凸包，可以直接遍历求出$O(|S|)$，也可以用隐式树状结构作询问（如某方向最远点）

空间复杂度$O(n)$

凸壳结构

注意到每次合并，新建的节点的左儿子是左子树的一段前缀，右儿子是右儿子的一段后缀，我们也可以用cls的可持久化平衡树方法来实现，从而显式地表达出凸壳结构

前缀、后缀刚好就是可持久化treap的spilt操作。时间复杂度不变（常数就不知道变不变了），空间复杂度$O(n\log n)$

好处是表示出了凸壳上的点集本身，有更多的应用；合并复杂度严格$O(\log n)$，不与深度挂钩

思考

如何维护一段凸壳上的点信息？（询问凸包面积）

注意可持久化treap是定义在我们的树结构上的~~（而且这违背了我们不写可持久化平衡树的初心）~~

我们已经用树结构维护了点集，有着天然的树结构。可持久化平衡树是必要的吗？

凸壳的可持久化树结构

我们称叶子节点维护一个点，非叶子节点维护一条$bridge$的树状结构称为“外部树结构”。

凸壳上的点在树中是子树里叶子的一个子集，其在外部树结构中形成的虚树称为“隐式凸壳结构”。

合并左右子树时，新的凸壳为左凸壳的前缀+$bridge$+右凸壳的后缀，而隐式凸壳结构的前缀后缀可以由$O(d)$个它的子树表示。（设$d$为深度）

考虑现在有一棵二叉搜索树（二叉搜索树的中序遍历是一个有序序列），想要知道二叉搜索树表示的有序序列的一个前缀它表示的是什么。

考虑最后的一个点在哪里

举个例子，比如它在这里：

那么所有小于它的点会形成一堆子树（除了一些根到它的几个单点）

就相当于从根往下搜索搜它的时候，每次往右走的时候它的左边都会比它小，并且上面还有一些比它小的点

所以一定可以被$O(d)$个子树来表示，即一个深度为$d$的二叉搜索树的一个前缀或者后缀一定可以由$O(d)$个子树表示。

所以我们可以使用可持久化树结构维护每个点的隐式凸壳结构。

因为就相当于可以在隐式数据结构上找出它的那些前缀和后缀的子树的组成了。那么直接新建一个点，然后把那些点的指针连向那些子树，这样就相当于用可持久化的树状结构维护它的隐式凸壳结构。（其实这就是显式的了）

可持久化树？

可持久化树实际上是一个DAG。对于一个点，它维护的信息实际上是它在DAG上不去重的dfs搜索树中所有点的信息和。（一个点可能会重复贡献信息）

相当于是一个树的压缩结构。

考虑有一棵树长这个样子，有两个子树是完全相同的：

那么并不需要用树结构把它拷贝一遍，考虑用两个边表示它在树的儿子里出现了两次

可就是说可持久化树对于每一个点都是表示一棵树，这个点表示的树就是由它指向的点的树依次排成的

所以说最后没有真正地把树维护出来，只是维护了一个类似DAG的东西，那么在DAG上进行dfs的时候就相当于把这棵树展开了。

凸壳可持久化树结构

一个点的凸壳集合可以表示为$O(d)$个点的已有可持久化树结构维护的集合的并，这$O(d)$个点在merge过程中即可求出（一个二叉树的$d$个点在当时二分的过程中已经搞出来了，即已经找出前缀和后缀的分界点，就用分界点将子树给取出来）。（$d$为该点子树深度）

除了“外部树结构”外，我们称我们维护凸壳的可持久化树结构为“内部树结构”。内部树的每个可持久化节点具有$O(d)$条出边（指向儿子的可持久化树结构的那棵树$\log$个节点）。

注意我们的修改操作并不会修改“内部树结构”，只会抛弃一些历史版本再加入一些新的版本。对于维护凸壳信息，只需要信息可加性即可。

该结构应该被认为是定义在外部树结构节点上的一种可加信息，它具有天然的可持久化性（想做可持久化完全动态凸包的话，只需要把外部的树结构给可持久化掉，内部的东西本来就支持可持久化），可以支持历史版本回归。

完全动态凸包总结与应用

我们本质用树状结构（“外部树结构”）按照坐标顺序维护了点集，并维护了在这个树状结构上定义的可加信息$bridge$，以此维护出了隐式凸壳结构。

我们也可以显式地使用可持久化树维护凸壳结构（“内部树结构”），虽然空间复杂度会变成$O(n\log n)$，但是可以进行与凸壳点集相关的询问。（如凸包面积）

操作时间复杂度严格$O(\log^2 n)$。

由于是可加信息（类似区间和，区间矩阵的积），应用十分广泛，可以有很多推广。比如说我们可以区间增加/修改$y$坐标，区间翻转$y$坐标（这里假设我们按照$x$坐标排序），也可以再加上可持久化。~~（传说中的可持久化平衡树套可持久化平衡树）~~

[NOI2017]分身术 uoj319

给定一个点集，每次询问删除其中$k$个点后形成的凸包面积，强制在线

$n\leq 10^5,M=\sum k=2\times 10^6$

删除$k$个点后的凸壳相当于$k+1$个区间的凸壳的并

直接用动态凸包维护可以做到$O(M \log^2 n)$或用论文实现$O(M \log n)$

可以预处理线段树区间每个前缀后缀的凸壳信息，这样任意一个区间可以通过某个前缀+某个后缀合并而成（似乎就是猫树）。

线段树在区间询问时是把一个区间拆成$\log$个区间合并起来。每次有一个中点，查询区间一定有一次跨过中点，然后此时考虑直接用左儿子的后缀以及右儿子的前缀把它合并起来。那么前缀和后缀的个数总共为$O(n\log n)$个，在本题中是预处理$O(n\log n)$个凸壳的信息。然后这道题就不管完全动态凸包了，考虑最简单的两个凸包合并，现在是有一个$O(\log)$的算法合并凸包，并且没有低于$O(\log)$的做法合并凸包。然后这道题询问$k$个点相当于询问$k+1$个区间的凸包的并，对于每个区间如果我们在线段树上查询凸包信息再合并起来那每个区间都会变成$O(\log)$个凸包的合并，那么再乘上$O(\log)$的合并复杂度，总时间复杂度就变成了$O(M\log ^2 n)$。然后这题有个优化，多预处理一些东西，线段树其实可以理解成预处理$O(n)$个区间信息，然后这些区间是长成一个线段树的形状的，然后方便我们之后把它分开成$\log$个区间。现在相当于预处理$O(n\log n)$个线段的信息，就把任意询问区间拆成$2$个区间。

然后就预处理复杂度多了个$\log$，询问的复杂度少了个$\log$。

总复杂度$O(n\log^2 n+M\log n)$（看起来能过）

其他几个凸包算法

假设只需要询问某个方向最远点

比如有一条斜率固定的直线，然后从下往上扫，求最后经过的点是哪个点。几何意义就是上面这个，代数意义就是找一个$\max{a_x+b_y},(x,y)\in S$，其实就是跟直线的法线点积的最大值。在很多斜率优化都可以用到，找最大值就维护上凸壳，找最小值就维护下凸壳。

性质：

对于询问点集可以拆分后再取$\max$

若询问的斜率具有单调性可以使用two pointer优化

对于单个凸包：

离线可以将询问按斜率排序，再用two pointer$O(n)$

在线需要二分，单次$O(\log n)$

对于区间询问某个方向最远点，可以用线段树拆分成$\log$个询问

如果坐标单调且只有加点操作（只在凸包右侧加点），可以只建线段树的一部分（等价于二进制分组）

假如现在有$k$个东西且坐标单调，然后将$k$写成二进制。

如$k=2^{a_1}+2^{a_2}+\ldots + 2^{a_l}$，

然后将前$2^{a_1}$个元素并起来（信息具有可加性），即将信息和算出来。然后再把$2^{a_2}$元素并起来，然后这样一直排列下去，就相当于把前$k$个信息分成$\log$组。二进制分组的典型应用就是凸包的最远点问题，因为两个凸包合并是$O(n+m)$的，所以合并的复杂度非常大，用二进制分组就考虑每次二进制个位都加1，如果二进制分组进行了一个进位的话就相当于把两个小块合成了一个大块，可以想象成一个一维的2048，总时间复杂度为$O(n\log n)$（$2^k$被合成了一次，$2^{k-1}$次方被合成了两次，$2^{k-2}$次方被合成了四次……）用二进制分组建单调这些点的凸包，对于每一组因为坐标单调所以可以$O(\log)$的区间查询最远点。所以加点的均摊复杂度是$O(n\log n)$的，查询复杂度为$O(\log^2)$。

考虑一个足够长的$2^k$方长的线段树，然后二进制分组就相当于把线段树的前$[1,m]$结构建出来

就比如前$1$个只有这个：