斜率优化 & wqs 二分 学习笔记

Part 1 斜率优化

在线维护两种操作：

• 插入直线 $(k_i,b_i)$；
• 给定 $x$，查询 $k_ix+b_i$ 的最大/最小值（可能有第二关键字）；

保证 $k_i$ 单调，$x$ 单调。

这里以 $k_i$ 单调不降，$x$ 单调不增，查询最小值为例。

直接做也可以，但是我写了调不出来。

首先做一个神秘转化：把直线变成点 $(k_i,b_i)$，查询的时候变成求过 $(k_i,b_i)$ 的斜率为 $-x$ 的直线的最小截距：

考虑有两个点的情况，设它们分别是 $(x1,y1)$ 和 $(x2,y2)$（$x1<x2$）。观察它们的连线，其斜率为 $k=\frac{y2-y1}{x2-x1}$，不难发现 $-x=k$ 时它们对应的截距相同（红线），$-x>k$ 时 $(x2,y2)$ 更优（绿线），$-x<k$ 时 $(x1,y1)$ 更优（蓝线）：

暂时不考虑三点共线，考虑加入的第三个点 $(x3,y3)$，设其与 $(x1,y1)$ 连线的斜率为 $k_{1,3}$，$(x1,y1)$ 与 $(x2,y2)$ 连线的斜率为 $k_{1,2}$，则：

• 若 $k_{1,3}<k_{1,2}$（左图），则：

  • $-x<k_{1,3}<k_{1,2}$ 时 $(x1,y1)$ 更优；
  • $k_{1,3}<-x<k_{1,2}$ 时 $(x3,y3)$ 更优；
  • $k_{1,3}<k_{1,2}<-x$ 时 $(x3,y3)$ 更优；
  • $-x=k_{1,3}<k_{1,2}$ 时 $(x1,y1)$ 和 $(x3,y3)$ 均比 $(x2,y2)$ 优；
  • $k_{1,3}<-x=k_{1,2}$ 时 $(x3,y3)$ 更优；

  所以 $(x2,y2)$ 无论怎样都不优，可以直接抛弃；

• 否则 $k_{1,3}>k_{1,2}$（右图），则：

  • $-x<k_{1,2}<k_{1,3}$ 时 $(x1,y1)$ 更优；
  • $k_{1,2}<-x<k_{1,3}$ 时 $(x2,y2)$ 更优；
  • $k_{1,2}<k_{1,3}<-x$ 时 $(x3,y3)$ 更优；

而若三点共线，则若没有第二关键字则 $(x2,y2)$ 没用；否则设第二关键字为 $z1,z2,z3$，则 $(x2,y2,z2)$ 有用当且仅当 $z2<z1,z3$。

考虑四点共线的情况，由于插入的点满足 $x$ 升序，所以若前三个点均没被删掉，则必有 $z2<z1,z3$，则此时必然不满足 $z3<z2,z4$，那么 $(x3,y3,z3)$ 必然没用。

也就是说，仅判断 $z2$ 和 $z1,z3$ 之间的关系来决定 $(x2,y2,z2)$ 的去留可以保证最终的结构中不存在四点共线。

不难发现，有用的点构成一个下凸壳，即对于相邻三个点必有 $k_{1,2}\le k_{1,3}$ 也即 $k_{1,2}\le k_{2,3}$，即斜率不降；并且若没有第二关键字则不存在三点共线，否则不存在四点共线。

考虑处理询问，注意到查询的 $x$ 单调不增，即 $-x$ 单调不降。由于 $k_{1,2}\le k_{2,3}$ 且不存在四点共线，所以每个查询的最优决策点 $(x_{i},y_i,z_i)$ 一定满足 $x$ 单调不降，那么不断把不优的点删掉即可保证 $x$ 最小的点最优。

注意到插入时下凸壳只会在末尾插入/删除，且查询时只会在开头删除，那么可以使用双端队列来维护下凸壳，时间复杂度 $O(n)$。

代码如下：（带第二关键字）

template<typename T>
struct hull // k++ x-- min
{
	typedef long long ll;
	const __int128 ill=1;
	struct node
	{
		ll x,y;
		T vl;
	};
	inline bool cmp(node x,node y,node z) // y is useful
	{
		ll up1=y.y-x.y,dn1=y.x-x.x;
		ll up2=z.y-x.y,dn2=z.x-x.x;
		auto lft=ill*up1*dn2,rig=ill*up2*dn1;
		if(lft<rig) return true;
		if(lft==rig&&(y.vl<x.vl&&y.vl<z.vl)) return true;
		return false;
	}
	int ps=0;
	vector<node> q;
	inline void clr(){ps=0,q.clear();}
	inline void ins(ll k,ll b,T vl)
	{
		auto u=(node){k,b,vl};
		while(q.size()-ps>=2)
		{
			int sz=q.size();
			if(cmp(q[sz-2],q[sz-1],u)) break;
			else q.pop_back();
		}
		q.push_back(u);
	}
	inline pair<ll,T> que(ll x)
	{
		while(q.size()-ps>=2)
		{
			ll v1=q[ps].x*x+q[ps].y,v2=q[ps+1].x*x+q[ps+1].y;
			if(v1<v2||(v1==v2&&q[ps].vl<q[ps+1].vl)) break;
			else ps++;
		}
		return make_pair(q[ps].x*x+q[ps].y,q[ps].vl);
	}
};

Part 2 wqs 二分

给定一个凸壳，满足该凸壳加上直线后的极值点好求，求 $x=w$ 时 $y$ 的值。

经常用于去除 “恰好选 $k$ 个” 的限制。

注意到由于凸壳具有凸性，所以凸壳上的每个点都可能变成切点，且由于相邻点斜率单调，所以可以二分求出 $(w,y)$ 作为切点时的斜率。

切点 $(x,y)$：对于斜率 $k$，满足 $(x,y)$ 在凸壳上且过它的斜率为 $k$ 的直线和凸壳仅有 $(x,y)$ 一个交点；

并且注意到对于一个斜率 $k$，只需要将凸壳加上直线 $y=-kx$ 再求极值点即可求出切点。

那么仅需二分 $k$，将凸壳加上 $y=-kx$ 求出极值点 $(x,y)$（即切点），再根据 $x$ 与 $w$ 的大小关系进行二分即可。

若凸壳上存在多点共线，则为了保证正确性还需保证求出的切点 $(x,y)$ 满足 $x$ 最小/最大。

这样可以以一个 $\log$ 的代价去掉个数限制。

例题：P5633 最小度限制生成树