书接上回。
对于 wqs 二分的正确性的严格证明，我们可以看这个。或者说，我不会。
这是一个比较感性的证明方法。
我们现在有一个定义在一个区间上的抽象函数 \(\mathrm{f}\)，这个东西有以下几个性质：
- 我们可以在 \(\mathrm{O}(T)\) 的复杂度内求出 \(\mathrm{g}(x) = \mathrm{f}(x)+kx\) 的最值点；
- 这是一个凸函数。
给定 \(m\)，我们要求 \(\mathrm{f}(m)\)。
过程
以下默认函数上凸。其实上凸或者下凸是对称的。
我们只能求最值来着。想求任意值就只能在最值上动点手脚。
我们赋一个权值 \(k\)，定义 \(\mathrm{g}(x) = \mathrm{f}(x)-kx\)。我们求 \(\mathrm g\) 的最值点，如果最值点为 \(x = m\) 那么直接得到 \(\mathrm{f}(x) = \mathrm{g}(x) + kx\) 然后就做完了。
那 \(x \neq m\) 怎么办呢？
我们发现 \(\mathrm{g}\) 的本质是拿一个斜率为 \(k\) 的直线来切这个凸壳，若求得 \(\mathrm{g}\) 有最值 \(y'\)，那么切线的纵截距即为 \(y'\)（想一想，能方便理解），当然纵截距本身不重要，重要的还是切点的横坐标。
在脑海里想象一个凸壳就可以发现，如果横坐标偏大则加大斜率 \(k\)，否则减小 \(k\)。
于是做完了。