适用范围
wqs 二分可以用来解决类似这样的问题：
令 \(f(x)\) 为恰好使用 \(x\) 次某种操作，求 \(f(p)\)。
\(f(x)\) 具有凸性（图像为上凸或下凸）。
对于一个值 \(k\)，若是下凸壳能较快的求出 \(\min\limits_{i = 1}^n\{f(i) - k\cdot i\}\)，上凸壳能较快的求出 \(\max\limits_{i = 1}^n\{f(i) - k\cdot i\}\)。
解法
接下来以下凸壳为例。
例如这个下凸壳：
现在 \(p = 3\)，即想要求 \(f(3)\)。
但是现在只知道这是个下凸壳该怎么办？
考虑利用下凸壳的性质，对于 \(i < j < k\)，\(\frac{Y_j - Y_i}{X_j - X_i}\le \frac{Y_k - Y_j}{X_k - X_j}\)，即过 \((X_i, Y_i), (X_j, Y_j)\) 的直线的斜率一定 \(<\) 过 \((X_j, Y_j), (X_k, Y_k)\) 的直线的斜率。
于是可以想到找到斜率 \(k\) 使得这条直线与下凸壳的切点就是 \((x, f(x))\)。
对于斜率 \(k\) 考虑二分。
假设当前的斜率为 \(k'\)，算出这条直线与这个下凸壳的切点 \((x, f(x))\)。
然后再通过比较 \(x\) 和 \(p\)，就可以得出当前的 \(k'\) 与 \(k\) 的大小关系。
如下图：
对于绿线，\(x = p\)，显然其是一个符合条件的 \(k\)。
而对于红线，其切点在 \((4, 1.5)\)，根据图象得到若 \(x > p\) 则 \(k' > k\)。
再对于蓝线，其切点在 \((2, 3)\)，根据图象得到若 \(x < p\) 则 \(k' < k\)。
接下来考虑对于斜率 \(k\) 找到切点 \((x, f(x))\)。
考虑斜率 \(k\) 的直线过每个点的直线的解析式 \(g(x') = f(x) + k(x' - x)\)。
再考虑因为是切点，选取截矩最小的一条直线，否则这条直线肯定会进入凸壳内部。
如图：
而发现截矩就是 \(f(0) = f(x) - kx\)。
所以只需要能较快的求出 \(\min\limits_{i = 1}^n\{f(i) - k\cdot i\}\)，并在过程中维护对应的 \(i\) 即可。
于是就可以得到最终的斜率 \(k\) 了。
那么最终的答案就是对于这个 \(k\) 像刚刚那样求出 \(\min\limits_{i = 1}^n\{f(i) - k\cdot i\}\)，最后再补上 \(k\cdot p\) 即可。
正确性：因为保证了对于这个斜率 \(k\) 的切点是 \((p, f(p))\)，所以 \(\min\) 是一定会在 \((p, f(p))\) 这里取到的。
对于上凸壳大致相同，大概把不等式方向换换即可。
注意事项
\(1\)：
根据下凸壳的求截矩时用的是 \(\min\) 可以看出下凸壳适用于求 \(\min\)。
相对的，上凸壳适用于求 \(\max\)。
\(2\)：
关于斜率 \(k'\) 对应选出切点对最后二分出的 \(k\) 的影响。
考虑到多点共线的情况，如下：
此时对于斜率 \(k'\)，\((5, f(5)), (6, f(6)), (7, f(7))\) 共线。
那是不是随便选一个切点即可呢？这是不行的。
考虑到若选取了切点 \((6, f(6))\)，则不管是如何判断 \(x, p\) 的大小都会至少漏掉 \(p = 5 / 7\) 中的的情况。
若是 x == p -> k = mid，那显然两种都会漏掉；若是 x <= p -> k = mid 则会；漏掉 \(p = 5\)；否则会漏掉 \(p = 7\)。
最好的处理办法是维护横坐标最大或最小的切点。
例如求出 \(\max\{x\}\)，若 \(\max\{x\}\ge p\) 则说明 \(k\le k'\)；求出 \(\min\{x\}\) 则是若 \(\min\{x\}\le p\) 则说明 \(k\ge k'\)。
例题
咕咕咕