凸包学习笔记

内容好多啊。

概念

\(n\) 个点形成的凸包，指的是在坐标系上这 \(n\) 个点构成的包含所有点的，以这 \(n\) 个点中的一些为顶点的极小的凸多边形。而一个凸包又由两部分组成，分为上凸壳和下凸壳（其实和凸包区分性不大），可以理解为这个凸多边形的上半部分和下半部分。

常见场景

维护凸包

题目明确提出需要你维护一个凸包的信息，例如周长、面积，此时可以使用凸包直接维护。

最优解问题

相信大家对这个场景其实并不陌生，因为单调队列优化 \(\text{dp}\) 本质上就是这个场景的一部分。这种场景通常需要你找到最优解，此时你需要先构造出形如 \(\dfrac{y_i-y_j}{x_i-x_j}>k\) 形式的式子来表示当 \(x_i>x_j\) 时 \(i\) 比 \(j\) 优的条件。考虑和单调队列优化 \(\text{dp}\) 相同的思路，我们发现最优解一定在当前所有决策点的凸包上，因此使用单调栈维护凸包即可。因为凸包的斜率具有单调性，所以我们只需要在上面二分就可以找出最优解，不难看出复杂度是 \(O(\log n)\) 的。

需要注意的是，如果 \(k\) 满足单调的性质，那么当前不优的点之后一定不优，于是可以使用单调队列省掉 \(\log n\)，做到 \(O(1)\) 的复杂度，这也是单调队列优化 \(\text{dp}\) 的做法。也可以利用这一点来进行复杂度优化。

常见用法

普通场景

这种场景通常表现为所有点可以在构建凸包前预先知道并排序，或保证在插入凸包时元素有序。在这种情况下，我们可以直接插入单调栈的最后方从而简单维护。

#define il inline
#define pii pair<int,int>
#define fi first
#define se second

const int N=1e5+5;

pii operator -(pii x,pii y){return {x.fi-y.fi,x.se-y.se};}
int operator *(pii x,pii y){return x.fi*y.se-x.se*y.fi;}//向量叉积，值 >0 时前者的斜率小于后者

int top;
pii stk[N];

il void Insert(pii x){//将当前点插入上凸壳
    while(top>=2&&(x-stk[top-1])*(x-stk[top])>=0)top--;
    stk[++top]=x;
    return ;
}

动态插入

这种场景通常表现为插入的点不一定有序，并且无法预先排序。在这种情况下，我们只能在凸包的中间插入点，并且通过插入点的状态进行动态维护。更具体的，对于当前点 \(P\) 前的点 \(A\)，后的点 \(B\)。如果 \(A\to P\to B\) 不满足凸包性质，则不会将 \(P\) 加入凸包。否则判断 \(P\) 前的两个点 \(A_1,A_2\)，如果 \(A_1\to A_2\to P\) 不满足凸包性质，则将 \(A_2\) 弹出。对于后方的处理同理。或者可以二分前方最靠后的一个点 \(A_1\) 使得对于 \(A_1\to A_2\to P\) 来说不满足凸包性质。可以使用 set 或平衡树实现，复杂度会因为数据结构自身多带一个 \(\log\)。查询时二分可以正常进行。

set<pii>con;
il void Insert(pii x){
	auto p1=con.lower_bound(x),p2=p1--;
	pii a=*p1,b=*p2;
	if((b-x)*(x-a)<=0)return ;
	auto tmp=p2++;
	while(true){
		if(p2==con.end())break;
		a=*tmp,b=*p2;
		if((b-a)*(a-x)>0)break;
		p2=con.erase(tmp);
		tmp=p2++;
	}
	tmp=p1--;
	while(true){
		if(tmp==con.begin())break;
		a=*p1,b=*tmp;
		if((x-b)*(b-a)>0)break;
		p1=con.erase(tmp),p1--;
		tmp=p1--;
	}
	con.insert(x);
	return ;
}

区间凸包

这种场景通常表现为需要编号在 \([l,r]\) 之间的点的凸包。需要注意的是，所求的凸包与整体凸包的编号在 \([l,r]\) 之间的点所构成的凸包不等价，原因在于一定优于 \(x\in[l,r]\) 的某个点 \(y\) 不一定也在 \([l,r]\) 中。考虑利用线段树维护，那么我们可以将区间 \([l,r]\) 分成 \(O(\log n)\) 段区间，这样我们只需要每次对线段树上的每个区间的凸包进行维护，插入点时只会修改 \(O(\log n)\) 个线段树上的区间。因为凸包分组后维护的全局最优解不变，因此这种做法适用于所有最优解问题而不适用于凸包信息问题。答案的查询可以正常二分，复杂度会因为数据结构自身多带一个 \(\log\)。

struct SegTree{
    #define lid (id<<1)
    #define rid ((id<<1)|1)
	int tot;
	vector<pii>hul[N<<2];
	void Insert(int id,int l,int r,int p,pll x){
		int tmp=(int)hul[id].size();
		while(tmp>=2&&(x-hul[id][tmp-2])*(x-hul[id][tmp-1])<=0)hul[id].pop_back(),tmp--;
		hul[id].push_back(x);
        //注意这里对凸包的维护受插入特点的影响，如果是动态插入的场景，需要利用树套树
		if(l==r)return ;
		int mid=(l+r)>>1;
		if(p<=mid)Insert(lid,l,mid,p,x);
		else Insert(rid,mid+1,r,p,x);
		return ;
	}
};

动态修改

这种场景通常表现为操作会对凸包中的点的位置造成影响。考虑修改对凸包的影响是不可估量的，于是我们只能采用暴力重构的方法，查询可以正常二分。考虑分块，若块长为 \(L\)，块数为 \(B\)，则暴力重构的复杂度是 \(O(L)\)，单次查询的复杂度是 \(O(B\log L)\)，简单将块长设为 \(\sqrt{n}\) 就有 \(O(\sqrt{n}\log n)\) 的复杂度。但由于分块之后无法维护准确的凸包信息而只能用于最优解问题。

il void Update(int id){
	int top=0;
	for(int i=st[id];i<=en[id];i++){
		while(top>=2&&(nod[i]-stk[id][top-1])*(nod[i]-stk[id][top])>=0)top--;
		stk[id][++top]=nod[i];
        //注意这里对凸包的维护受插入特点的影响，如果是动态插入的场景，需要利用平衡树
	}
	return ;
}
il void Modify(int p,pii x){
	int P=pos[p];
    nod[p]=x;
    Update(P);
	return ;
}

动态删除

这种场景通常表现为会删除某一些点。这种场景的做法非常之多，需要结合题意分析。

正难则反

对于离线并且只有删除操作的题目，显然我们可以转换操作顺序，将删除看作增加，于是可以在正常的复杂度内简单求解。

分块

显然删除也可以利用暴力重构思想，直接利用分块可以做到 \(O(\sqrt{n}\log n)\)。显然只适用于最优解问题。

线段树分治

考虑在一些题目中，可以将同一个点的增加和删除看作存在性的改变，对于每一个询问都存在一些点存在。考虑维护每一个点存在的时间 \([L,R]\)，在线段树上维护凸包，在遍历线段树的时候得出答案，因为数据结构自身，复杂度会多一个 \(\log\)。显然只适用于最优解问题。

洋葱算法

考虑贪心。如果题目只删除一个点，当这个点不在凸包上时，我们发现凸包不变；当这个点在凸包上时，我们可以将这个点与两边点的连边去掉，设左边点的横坐标为 \(L\)，右边点的横坐标为 \(R\)，这样的操作会让下方 \((L,R)\) 之间的点露出来，我们只需要在这些点中选择可以插入的点即可。不难发现这样的点一定在除去第一层凸包的所有点后剩下的点构成的凸包上，因此我们维护两层凸包即可。将其拓展到一般情景，如果最多只会去掉 \(k\) 个点，那么我们只需要维护 \(k+1\) 层凸包，根据鸽笼原理，不管怎么选择 \(k\) 个点，都一定会有一层凸包不受影响，此时这层凸包是我们的起始凸包。接着我们将漏出点后寻找最优转化为选择完后覆盖无用，也就是说我们从内向外枚举每一层凸包，并维护在当前情况的答案凸包。对于新一层所有连续的未被删除的点的区间 \([L,R]\)，我们尝试将其覆盖到原来的凸包上。因为这个凸包在最外层，因此这段区间中的所有点一定都会被选中，考虑原凸包对答案凸包的贡献。显然在 \(L\) 左侧有一个最靠右的点 \(A_1\) 使得 \(A_1\to A_2\to P_L\) 不满足凸包的要求，右侧同理。将这样的两端从原来的凸包分割出来，合并到新段上即可，复杂度 \(O(nk+(n+\sum k)\log n)\)。

因为一层一层的凸包看着很像洋葱（？所以我叫它洋葱算法。