凸包技巧

Published: by Creative Commons Licence

  • Tags:

凸包技巧

假设一开始我们有一个空的集合$Y$。下面我们要支持下面几种操作:

  • 向集合插入一个一阶多项式。
  • 询问集合中所有一阶多项式在某个特定$x=x_0$值处的值的最大值。

两个操作发生次数都不会超过$10^6$次,并且询问之前一定保证集合非空。

很显然暴力是不好的,暴力是解决不了问题的,暴力的时间复杂度是$O(nm)$,$n$为插入执行次数,$m$为询问执行次数。

小学数学就教过我们,一阶多项式为$y=ax+b$,它一定是一条直线。如果$a$为正数,那么直线一定是递增的,如果$a$为负数,则直线对应是递减的,如果$a$为0,则直线是水平的。

我们记一个新的函数$f$,定义为:

由于一阶多项式是连续的,因此$f$也是一个连续函数。它的实际表现是一幅折线图。

对于集合中的某个一阶多项式$y$,如果对于任意$x\in [l,r]$,都有$y(x)=f(x)$,则称$[l,r]$为函数$y$的优势区间。如果$Y$中函数没有优势区间,那么我们可以将其从$Y$中剔除而不影响查询的结果。稍加推导就可以证明一个函数的优势区间一定是连续的,所有函数的优势区间是互不相交的(两个区间端点分配给任意一个一阶多项式),且所有函数的优势区间的并一定是全域。

我们称一阶多项式$y$的优势区间中的下确界为$y$的起始作用点。很显然起始作用点和直线的斜率是息息相关的,斜率越大,起始作用点越大。我们可以利用这个性质,维护一个有序集合,集合按照直线的斜率排序(对应的也是按照起始作用点排序)。

下面说明如何完成两种操作。

对于插入操作,我们对集合进行二分查找,找到插入点。如果集合中存在与插入直线拥有相同斜率的直线,那我们就选择处于上方的那一条。之后处理插入点的前驱,计算前驱与插入直线的交点,如果交点在前驱的起始作用点之前,那么前驱就会被插入直线完全覆盖,于是从集合剔除前驱,之后继续处理前驱。处理完前驱后以类似的方法处理后继,计算后继与插入直线的交点,如果交点在插入直线的起始作用点之前,那么插入直线就没有插入的意义,如果交点在后继的后继的起始作用点之后,后继就会被插入直线完全覆盖,剔除后继后,重复流程。 对于查询操作,我们对集合进行二分查找,找到所有起始作用点不大于$x_0$的直线中拥有最大起始作用点的那个函数$y$,此时$f(x_0)=y(x_0)$。

查询操作,很显然时间复杂度是二分查找的时间复杂度,为$O(\log_2n)$。

插入操作,我们可以让每个插入直线负责自己的整个生命周期,每个插入直线的生命周期仅为插入和删除两种,时间复杂度都是$O(\log2_n)$,因此插入操作的摊还时间复杂度可以认为是$O(\log_2n)$。

李超线段树

李超线段树的原文可以在线段树找到。

我们稍微修改一下上一节的问题,这次我们插入的不是直线,而是线段。即插入的一阶多项式的作用域是某个有限区间而非全域。

这个问题我们就无法拿凸包技巧来解决。下面我们提供一个插入时间复杂度为$O((\log_2n+m)^2)$,查询复杂度为$O(\log_2n+m)$的解决方案。

首先,如果线段区间,查询的下标范围很大,我们可以先离散化,下面我们的分析将认为可能的作用域为${0,1,\ldots,O(n+m)}$。我们可以建立一个线段树,每个线段树结点维护的是一条线段。我们知道线段树结点包含区间的概念,而结点保存的线段必定是作用域覆盖了整个结点区间的线段。这种线段可能有很多,我们在每个结点仅保存其中的一个。

对于插入操作,我们按照线段树的规则进行递归更新。如果线段的作用域完整覆盖当前所在结点的区间,那么执行下面流程。如果结点还未保存任何线段,则记录线段,并结束。否则,我们就计算保存的线段和插入线段的交点。

如果交点处于区间中间的左侧,那么我们就将结点记录的线段更新为两条线段斜率较大者,之后对左子结点下传斜率较小者。否则,我们就将结点记录的线段更新为两条线段斜率较小者,对右子结点下传斜率较大者。一次线段树更新会涉及$O(\log_2n+m)$个结点,而每次下传到完整覆盖区间后,就仅单向下传最多$O(\log_2n+m)$次,因此更新的时间复杂度为$O((\log_2n+m)^2)$。

由于我们每次都会将插入直线下传到它可能的优势区间,因此优势区间包含$x_0$的线段一定记录在某个对于区间包含$x$的结点中。实际上如果这个线段没有记录在$[x,x]$对应的结点中,就意味着它没有下传,换言之保存在了$[x,x]$的某个祖先结点中。

对于查询操作,我们从上至下遍历所有区间覆盖$x_0$的结点,并计算它们保存的一阶多项式在该点的值中的最大值,由于包含$x_0$的区间最多有$O(\log_2n+m)$个,因此时间复杂度为$O(\log_2n+m)$。

提供一道BZOJ1007

单调增斜率优化

首先让我们来考虑下面问题:

要求求解$f(n)$,其中$f$定义如下:

其中h是一个已知函数,而s是一个严格递增函数。这里我们简单记$r(j,i)=f(j)+h(j)-s(i)s(j)$。

可以很轻松地给出一个$O(n^2)$时间复杂度的算法,但是假如你学会了斜率优化,那就能将时间复杂度降低为$O(n)$。

假设存在$k<j<i$,且$r(j,i)\leq r(k,i)$,那么我们可以推得:

看着上面公式是不是有点眼熟?让我们记Y(i)=h(i),记X(i)=s(i),那么带入上面公式得到:

这时候应该认出来了吧,这就是我们的斜率公式,即不等式的左边表示的是从$(X(k),Y(k))$出发到点$(X(j),Y(j))$的直线斜率。这里我们简单记$g(k,j)=\frac{Y(j)-Y(k)}{X(j)-X(k)}$。

注意我们两个公式是以等价的方式推导出来的,即$r(j,i)\leq r(k,i)$当且仅当$g(k,j)\leq s(i)$成立。

假设存在三个点$t<k<j<i$,且$g(t,k)\geq g(k,j)$,那么我们可以发现,如果$r(k,i)\leq r(t,i)$,这意味着$g(t,k)\leq s(i)$,但是考虑到$g(k,j) \leq g(t,k)$,因此可知$g(k,j)\leq s(i)$,从而推出$r(j,i) \leq r(k,i)$。换言之,$f(i)$永远拥有比$r(k,i)$更好的选择,因此我们可以在计算$f(i)$时不考虑$f(k)$。

由于之前推出的结论,我们发现真正需要被考虑的点$(X(i_1),Y(i_1)),(X(i_2),Y(i_2)),\ldots$,其必然有斜率递增的特性,即$g(i_{m-1},i_{m})\leq g(i_{m},i_{m+1})$。因此我们只需要利用一个双端队列维护一个斜率递增的点集,考虑到$s(i)$严格增的性质,我们就可以在$O(n)$的时间复杂度内计算$f(1),\ldots ,f(n)$。

凸包技巧的应用

区间凸包技巧:给定$n$条直线,第$i$条可以表示为$f_i(x)=a_ix+b_i$。现在给出$m$个请求,每个请求给定$l,r,x$,要求回答$\max_{l\leq i\leq r} f_i(x)$。其中$n,m\leq 10^5$

暴力的时间复杂度是$O(nm\log_2n)$,是不可取的。我们可以利用离线二分的技术,时间复杂度为$O(n(\log_2n)^2+m\log_2n)$,还是非常快的。

子树凸包技巧:给定一颗$n$个顶点的树,顶点$i$保存一条直线$f_i(x)=a_ix+b_i$。之后给出$m$个查询,第$i$个指定一个顶点$u_i$以及一个整数$x_i$,要求回答以$u$为根的子树中保存的所有直线在$x_i$处取值的最大值。

这个问题可以通过树上启发式合并解决。

路径斜率优化:给定一颗$n$个顶点的树,顶点$1$为根,每条边有边权,现在我们希望从每个顶点出发坐巴士前往顶点$1$,允许在任意站点换乘。假设从顶点$i$坐巴士出发,乘坐$x$公里,那么费用为$a_ix+b_i$。现在要求计算每个顶点出发到顶点$1$的最小费用。所有边权均为正数,且满足顶点$i$距离顶点$1$越远,则$a_i$越大。$n\leq 10^5$

可以发现我们实际上要在每个顶点处,维护所有祖先顶点信息组成的一个凸包。但是难点在于凸包不支持删除操作。

这里有两种做法,第一种就是发现凸包的新增和删除是栈式操作,这意味着我们可以利用持久化数据结构避免删除操作(不带路径压缩的并查集也可以利用这个技术实现持久化)。这样我们可以利用$O(n\log_2n)$的时空复杂度解决这个问题。

还有一种很神奇的方式。注意到从根到任意顶点路径上,$a$属性是严格递增的,因此我们可以利用斜率优化代替凸包技巧。那么斜率优化对比凸包技巧的有点是啥?斜率优化的修改操作只会修改$O(1)$的数据,即一次斜率优化,我们会修改队列头部,队列尾部,以及队列尾部的元素,只有3个信息。因此我们很容易对其实现恢复操作。但是斜率优化的时间复杂度是摊还的,其在序列上拥有正确的$O(n)$时间复杂度,但是在树形结构上时间复杂度会劣化到$O(n^2)$。但是由于队列中保存的顶点满足斜率递增的性质,因此我们可以用二分来快速寻找新的队头和队尾,这样就能保证时间复杂度为$O(n\log_2n)$。

提供一道原题

路径凸包技巧:给定一颗$n$个顶点的树,顶点$1$为根,每条边有边权,现在我们希望从每个顶点出发坐巴士前往顶点$1$,允许在任意站点换乘。假设从顶点$i$坐巴士出发,乘坐$x$公里,那么费用为$a_ix+b_i$,且从$i$顶点出发的巴士的终点站在$e_i$,即不能一次性从$i$到达$e_i$的祖先。现在要求计算每个顶点出发到顶点$1$的最小费用。所有边权均为正数。$n\leq 10^5$

这道题和路径斜率优化题目的区别在于,不保证离根越远的顶点的$a_i$越大,因此在这里斜率优化是不适用的。我们必须借助凸包技巧,但是这里也不能利用持久化技术,因为持久化必须保证删除是栈式的。

我们可以利用点分治解决这个问题(想不到吧)。假设我们在处理一颗子树$T$,我们首先搜出重心,如果重心不是子树中所有顶点的祖先,那么重心的所有祖先一定存在于某颗重心下的子树$S$中,我们将这个$S$先用点分治递归处理掉(点分治对子树的执行顺序没有要求),这个不会影响时间复杂度。之后我们将重心的DP直接暴力求出(仅考虑$S$对重心顶点DP的贡献),这一步时间复杂度不超过$|S|$,因此也不会影响总的时间复杂度。之后我们将重心下其余子树(除了$S$)中的所有顶点全部取出,按照其可以访问到的祖先顶点的深度进行排序,之后我们不断将$S$中的重心祖先加入到动态凸包中,同时不断计算对其余顶点的贡献,这一步的时间复杂度为$|T|\log_2|T|$。

这样我们最后就能得出结果,总的时间复杂度为$O(n(\log_2n)^2)$。

离线动态凸包技巧:处理$n$个请求,请求分三类。第一类:给定$a,b$,插入一条直线$y=ax+b$;第二类:删除第$i$次操作插入的直线;第三类,给定某个$x$,查询当前所有直线在$x$处最大值。其中$n\leq 10^5$。

整个问题唯一的难点就是支持删除上面。这里我们可以使用和利用线段树使并查集支持删除相同的技术。建立一个线段树,线段树的区间$[l,r]$表示在第$l$次请求到第$r$次请求之间存在的所有直线。

对于插入操作,我们可以通过离线确认这个直线删除的时间(如果永远不删除,那么把删除时间设置为$n+1$)。记时间$l$为当前请求编号(请求时间),$r+1$为删除时间,那么我们就将这条直线插入到线段树的区间$[l,r]$中。线段树每个结点中维护一个凸包技巧,由于凸包不支持上推操作,因此这里我们也不下压脏标记,只是在每次查询的时候,路径中的所有顶点中维护的凸包技巧都对结果进行贡献即可。

删除操作于是乎就嗖的一下,不见了。

每次操作最多修改$\log_2n$个顶点中维护的凸包技巧,或者查询$\log_2n$个顶点中的凸包技巧,因此每个操作的时间复杂度均为$O((\log_2n)^2)$。

二维凸包

一个多边形,如果任意两个顶点之间连线上所有点都落在多边形内,则称这个多边形为凸包。

给定$n$个点,其中至少有三个点不共线,我们可以通过Graham scan算法在$O(n\log_2n)$的时间复杂度内计算凸包。如果只需要求上下凸包,也可以直接利用凸包技巧$O(n\log_2n)$求。

对于一个上凸包,第$(x_i,y_i)$为从左往右数第$i$个凸包上的顶点,则一定有$2y_i>y_{i-1}+y_{i+1}$。而对于一个下凸包,则正好相反,有$2y_i<y_{i-1}+y_{i+1}$。

题目1:给定$n$个顶点,要求计算最远的两个顶点的距离

不难发现,最远的两个顶点一定在凸包上,且一定是凸包的顶点。因此可以先$O(n\log_2n)$搞出凸包。但是如果数据设计的就是给定的$n$个点恰好就是凸包上的顶点,那么接下来的暴力枚举还是需要$O(n^2)$的时间复杂度。

这里我们可以使用另外一种技术,叫做旋转卡壳算法,就是维护两个平行线,分别切凸包上下两个顶点,且不停旋转。可以发现最远的两个顶点一定在两个平行线于凸包的切点处。而切点总数为$O(n)$,因此总的时间复杂度为$O(n)$。

题目2:给定$n$个数$a_1,a_2,\ldots,a_n$,要求输出另外一个序列$b_1,\ldots,b_n$,其中满足$b_1=a_1,b_n=a_n$,而对于任意$1<i<n$,需要满足$b_i=\max(a_i,\frac{b_{i-1}+b_{i+1}}{2})$。如果有多个序列,则输出任意一个即可。

容易发现如果我们将每个数$a_i$看作一个顶点$(i,a_i)$,并在这些顶点上建立一个上凸包,那么可以直接取$b_i$为凸包上边界中坐标为$i$处的高度。可以发现这样得到的$b_i$一定满足条件(由于是上凸包,因此$b_i\geq a_i$是一定成立的,且上凸包保证了$b_i\geq \frac{b_{i-1}+b_{i+1}}{2}$)。

事实上我们还能证明解是唯一的。假设还有一组解,记作$c_1,\ldots,c_n$,满足$c_i=\max(c_i,\frac{c_{i-1}+c_{i+1}}{2})$,且$b\neq c$。我们设对于任意$j<i$,有$b_j=c_j$,且$b_i\neq c_i$。不失一般性可以认为$c_i>b_i$(否则我们可以交换$c$和$b$),那么很显然$c_i>a_i$,且$c_{i+1}-c_i=c_i-c_{i-1}$可以知道$(i,c_i)$与$(i-1,c_{i-1})$,$(i+1,c_{i+1})$共线。记$(k,c_k)$为最后一个与$(i-1,c_{i-1})$和$(i,c_i)$共线的顶点,则一定有$c_k\leq b_k$,但是由于$(k,b_k)$处于上凸包上,因此$c_k\leq b_k$是不可能满足的。即对于任意顶点$k\geq i$,都应该有$c_k>b_k$,这与$c_n=b_n=a_n$相悖,因此假设不成立。至此我们证明了解的唯一性。

由于凸包上的顶点已经按照横坐标排好序了,因此可以直接用个栈直接算出整个凸包,时间复杂度为$O(n)$。