wqs二分的一些细节

wqs二分的本质

• 我们要求一个答案函数$f[x]$中一个特定点的值。
• $f[x]$（即函数值）是有特殊限制的下求出的答案（特殊限制即变量$x$）。$f$是一个凸函数（凸包）。
• 如果我们可以构造一个函数$g[x]$（作为截距）使它没有特殊限制，并且可以轻易计算（一般通过对限制的选项加权，来构造函数$g$）。并且$g$和$f$有关于$x$的一次函数关系（类似于$f[x]=g[x]+k\ast x$），这时候我们就可以二分斜率来求答案。
• 因为斜率越大，与函数图像所切的点就会越靠前（vice versa），即$x$越小，最后二分到题目要求的$x$，就可以算出正确的答案。

wqs二分的一些细节

（针对整数二分）

• sit1.最后成功二分到准确点，直接输出答案。

• sit2.最后二分只剩下两个点的时候，必定是一个多了一个少了，那我们要做的就是找到哪一个是正确的斜率。方法很简单，设较小的一个斜率为$x$，则较大的斜率为$x+1$。若$x+1$的切点被$x$穿过，那么$x$是正确斜率，若$x$的切点被$x+1$穿过，那么$x+1$是正确斜率。

  形式化的说：若$f$和$g$的函数表达式为$f[x]=g[x]+k\ast x$，设$x$的切点为$a$，$x+1$的切点为$b$，若$x\ast b.x+g[x]=b.y$（已知的是$x\ast a.x+g[x]=a.y$），那么正确的斜率就是$x$。
  （以上切点是指当前斜率与凸包的切点，是一个二元组）

两篇分析wqs二分本质的blog

一个传送门
另一个传送门