下文中的 $\max/\min$ 可以为了严谨起见理解成 $\sup/\inf$。
众所周知，WQS 二分优化的是这样一类问题：有一个函数 $f(x)$，给定 $a$，希望求得 $f(a)$，但是 $f$ 的单点值无法快速求。这时，如果有以下性质之一：
- $f(x)$ 上凸，且能快速求 $\max_x\set{f(x)-kx}$。
- $f(x)$ 下凸，且能快速求 $\min_x\set{f(x)-kx}$。
那么就可以利用二分 $k$（也就是所谓的“多选扣分”）的方法“凑”出所需的 $f(a)$。
接下来只以满足第 1 种性质的 $f$ 为例。
常用的不严谨方法
问题出在二分判定的时候。常用的写法要求 check 函数返回一个取到 $\max$ 的 $x_0$ 值，然后与 $a$ 比较大小。如果 $x_0$ 是任选的，那么如果二分的斜率恰好正确，而切线上有多于一个点（所谓“共线情况”），那么 $x_0$ 与 $a$ 的大小关系是任意的。而由于整数二分一定有一边会排斥掉 $mid$，故这个做法是错误的。
相应的弥补方案有两种。一种是 check 返回最小或最大的 $x_0$。例如返回最小的 $x_0$，如果 $x_0\le a$，那么 $r\gets mid$，否则 $l\gets mid+1$。另一种是实数二分，其正确的原因在于总是不排除 $mid$，这样正确的斜率总是包含在 $[l,r]$ 中，而如果整数二分这样做，就会在区间为 $[l,l+1]$ 时卡住。以 $l=1$ 为例：
实数二分考虑了这条红切线（$k=l+0.5$），因此可以区分绿点是在哪一边。
但是这两种处理方法面对着一个共同的问题，即高维的情况无法简易地处理：CF739E 和 CF1799F。
以二维的情况为例，有函数 $f(x,y)$，要求 $f(a,b)$（其中 $f(x,b)$ 关于 $x$ 是上凸的，且 $\forall,k,\max_x\set{f(x,y)-kx}$ 关于 $y$ 是上凸的）。这时外层二分的判定条件应该是“使 $f(x,b)-kx$ 取到 $\max$ 的 $x$ 值”，然而这个值是难求的。
你可能会说，内层二分的斜率 $k^\prime$ 已经求出来了，那拿它和 $k$ 一起跑一遍 check，尽量使 $x$ 最小或最大就行了呀。这里的问题在于，无法保证 $y$ 恰好取到 $b$，因为 $y$ 这一维同时也会出现共线情况，这时可能会取到错误的 $y$，从而取到不该取的 $x$。这个问题即使用实数二分也无法解决，例如这个提交记录。
一种解决方法
Neal Wu 在这里提出了一种精细的处理方法。例如要求最小的取到 $\max$ 的 $x_0$，那么在 check 中求出必须要用几个 $x$，必须要用几个 $y$，和既可以用 $x$ 又可以用 $y$ 但不能都不用（必须都用的情况不算在内，应算作前两个各自加一）的数量，分别记作 $\alpha,\beta,\gamma$。外层二分如果 $\alpha\le a\land \alpha+\beta+\gamma\le a+b$，那么 $r\gets mid$。这个判断的正确性如下：
- 如果这些条件不满足，那么显然不存在合法分配方案，斜率一定是太小了。
- 如果这些条件满足，那么一定存在一个 $x\le a$，使得 $f(x,b)$ 被切线切到。构造方法是，$y$ 先取 $\beta$ 部分，显然 $\beta\le b$（不然内层二分就不会二分到这个斜率）。然后尽量用 $\gamma$ 的部分补满 $b$。如果补满了，那么由 $\alpha+\beta+\gamma\le a+b$，故 $x=\alpha+\gamma-(b-\beta)$ 一定可以。如果没补满，那么找另一些不影响 $x$ 用量的元素补满 $y$（一定能补满，不然内层二分就不会二分到这个斜率），这时由 $\alpha\le a$，故 $x=\alpha$ 一定可以。
这里是另一题我写的类似的处理方法。
但是这个方法缺乏通用性。首先，刚才这个解法中“用”的定义只在这两题里成立（即用两类精灵球和用两类操作），如果没有类似的组合意义就不行了，所求条件就再次变成了不可解决的，类似于原问题的“强制限定 $y=b$”。其次，维数再高就难以讨论了。
通用的解决方法
核心性质：对于上凸的 $f(x)$，令 $g(k)=\max_x\set{f(x)-kx}+ka$，$g(k)$ 是下凸的，且最小值恰为 $f(a)$。（在力学中这个称为 Legendre 变换）
这张动图中红色轨迹即为 $g(k)$。
证 1：若 $f(k)$ 处处可导，令 $h(k)=\min\set{x\mid f^\prime(x)=k}$，则 $g(k)=f(h(k))-k(h(k)-a)$。 $$ \begin{aligned} g^\prime(k)&=f^\prime(h(k))h^\prime(k)-kh^\prime(k)-(h(k)-a)\\ &=kh^\prime(k)-kh^\prime(k)-h(k)+a\\ &=-h(k)+a \end{aligned} $$ 而 $h(k)$ 是递减的，故 $g^\prime(k)$ 递增。
证 2：用更加普遍的定义来证。同样令 $h(k)$ 为使 $g(k)$ 取到 $\max$ 的某个 $x$。$\forall,k_1,k_2$，对于 $\lambda\in (0,1)$，令 $k_m=\lambda k_1+(1-\lambda)k_2$： $$ \begin{aligned} &\lambda g(k_1)+(1-\lambda)g(k_2)\\ ={}&\lambda\max_x\set{f(x)-k_1x}+(1-\lambda)\max_x\set{f(x)-k_2x}+k_ma\\ \ge{}&\lambda(f(h(k_m))-k_1h(k_m))+(1-\lambda)(f(h(k_m))-k_2h(k_m))+k_ma\\ ={}&f(h(k_m))-k_mh(k_m)+k_ma\\ ={}&g(k_m) \end{aligned} $$ 同时，显然 $\forall,k,g(k)\ge f(a)$，又由于 $f$ 的凸性，一定存在一个 $k$ 使得 $g(k)=f(a)$，故得证。
另外我们会惊奇地发现：除了最后一步外，证 2 甚至没用 $f$ 的凸性！
于是就可以直接二分了，判定时只需比较 $mid$ 和 $mid+1$（或 $mid+\varepsilon$）的 check 结果。CF1799 的代码。
这样做唯一的缺点在于会有 $2^d$ 倍常数（$d$ 为维数）。可以用优选法（按黄金比划分的三分）优化到 ${1.44}^d$ 倍。
一个小细节
考虑实数二分的精度问题，设当前二分区间为 $[l,r]$，取 $f(h(l))-lh(l)+la$ 来估算答案，它与 $f(a)$ 的差距为： $$ \begin{aligned} \lvert f(h(l))-lh(l)+la-f(a)\rvert&=\left\lvert l(a-h(l))-\int_{h(l)}^af^\prime(x)\mathrm{d}x\right\rvert\\ &=\left\lvert\int_{h(l)}^a(l-f^\prime(x))\mathrm{d}x\right\rvert\\ &\le\lvert a-h(l)\rvert\cdot(r-l)\\ &\le\lvert I\rvert\cdot(r-l) \end{aligned} $$ 其中 $I$ 为 $f$ 的定义域。因此二分一般得在 $r-l$ 小于允许的绝对误差除以 $n$ 时才结束。$f(x)=C$ 时可以取到最差情况下的误差。
参考资料 & 总结
本文基本上就是 Theoretical grounds of lambda optimization 的提要版本。
目前，WQS 二分在应用中仍难以解决的问题主要是凸性的证明。大量题目直觉上目标函数具有凸性，但无法严格证明。归约费用流可能是一种有前途的方案，但目前这几道题例仍未找到证明。adamant 的这篇文章关于 CF739E 的证明应该是错的，我在下面的评论区也有提问，如果您有想法可以与我交流。
目前已知的证明方法：
[IOI2016] Aliens：四边形不等式是要的，然后有两个证明方法，分别于 Kubic 23 年的论文、我 24 年的论文。
CF739E 和 CF1799F：用题解区这篇的方法建图，然后把一种精灵球选的代价改为 $+\infty$，这样就可以证 $f(x,b)$ 或 $f(a,x)$ 的凸性；内层的凸性更容易，可以用流或 dp 证。这题外层不能用 dp 归纳证，分讨会有一种情况去世。
P1792 种树：这类题如果是奇环我是不会证的，并且我目前没看到对的证明。偶环、链、树这类二分图的情况可以看 Kubic 的论文。对于链的情况，可以将限制扩展到“任意两个选的距离必须 $\ge k$”，这样就只能用四边形不等式（一个区间的代价为除去开头 $k$ 个，剩余的 $\max$，这样就有四边形不等式了）或者 dp 归纳证。
[八省联考 2018] 林克卡特树：这篇题解似乎有证明，我没仔细看，不知道是否严谨。反正 dp 归纳是不行的。