DP 凸性优化：wqs 二分

发现自己阅读量最高的 wqs二分 有点简略，而且有些地方是错的，所以就重构了一下，并加入了更多的例题。
前面基本上都是照搬的原来那篇文章。
介绍

wqs 二分最初由王钦石在他的 2012 年国家集训队论文中提出，也叫"带权二分"，或者"dp凸优化"，而从 IOI 2016 的 Aliens 题目开始，这种方法开始逐步在竞赛圈中有了一定的地位。在国内我们一般称为「wqs 二分」，而在国外一般称为「Alien Trick」。
特征

wqs 二分的题目一般有以下特点:

• 题目内容形式为：有 \(n\) 个物品，从中选出 \(m\) 个，要求最后的权值最小/最大。
  
• 直接 DP 设 \(f_{i,j}\) 表示前 \(i\) 个选出 \(j\) 个物品的话，时间复杂度无论如何都是 \(O(n^2)\) 及以上的。
  
• 如果没有选 \(m\) 这个限制，那可以优化到更低复杂度，并且可以算出此时最优方案选的数的个数。
  
• 答案关于选的物品个数具有凸性，即如果设 \(g(x)\) 表示选 \(x\) 个物品可以得到的最小/最大权值，那么 \(g(x)\) 的图像构成一个凸包。
  

当然 wqs 二分不止应用于 DP 题，具体看例题。
算法

大致流程

假设 \(g(x)\) 的图像为上凸包，此时我们要求最大值，不妨画一下 \(g(x)\) 的大致图像(当然其实我们是一个点都求不出来的)：

假设我们现在用一条直线 \(y=kx+b\) 去切一个点 \((x,g(x))\)，那么可以得到 \(g(x)=kx+b\)，即这个点的坐标也可以表示成 \((x,kx+b)\)。
又因为上凸包有个性质，一条斜率为 \(k\) 的直线在他与这个凸包的切点处截距最大，也就是说如果我们能求出这个最大截距，并知道此时的横坐标，就能知道那个切点的具体坐标了。
因为凸包的斜率是单调的，所以随着 \(k\) 的减小，切到的 \(x\) 也越大，所以可以二分这个 \(k\)，然后根据切点的坐标去调整 \(k\) 直到切到 \((m,g(m))\) 为止。
现在的问题就是怎么求最大截距，因为我们压根不知道这个凸包长什么样子。
会发现 \(b = g(x)-kx\)，定义 \(h(x) = g(x)-kx\)，如果我们能以较低的复杂度求出最大的 \(h(x)\) 以及此时的 \(x\)，也就求出了我们要的东西。
考虑给 \(h(x)\) 定义一个合理的意义，不难发现他其实就是给每个物品多加了一个 \(-k\) 的权值，选了这个物品就要 \(-k\)。
而我们要求 \(h(x)\) 的最大值是没有限制要选多少个的，所以 DP 时只需要设一维即可，会更好求，具体的优化方法/求法因题目而异，在例题中会讲。
注意最后求 \(g(x)\) 时，要记得把 \(kx\) 加上。
实现细节——共线情形

当凸包上存在多个点共线的时候，我们二分的直线可能会同时切到很多点，如果我们最后求出来的 \((x,h(x))\) 是从中任取一个的话，会使得我们可能漏掉最终答案的位置。因此我们需要保证每次求出来的切点是所有可行切点中横坐标最小/最大的。以上凸壳为例，如果我们每次求出来的 \(x\) 是最小的，那么二分应该写的是 if(x=mid) l=mid+1,更新答案; else r=mid-1。
这是 wqs 二分最容易出错的点，在之后的例题中也会额外注明。
常见误区

• 由于相邻两点的横坐标之差是 \(1\)，所以此时斜率和差分没有区别，而当 \(g(x)\) 一定是整数时，斜率也一定是整数，因此我们二分也只需要二分整数域就一定可以切到要求的点；而当最后的答案可能是小数时，我们二分的斜率也应是实数域。
  
• 假设我们最终二分出来的斜率为 \(k\)，在 check 函数里求出来的是 \((x,h(x))\)，那么假设我们在共线的时候取的是 \(x\) 最小的，则我们只能保证 \(x\le m\)，即 \(x\) 不一定恰好就是 \(m\)，但是我们可以知道用斜率为 \(k\) 的线去切，切在 \(x\) 上和切在 \(m\) 上的截距都是 \(h(x)\)，因此最后的答案是 \(h(x)+km\)，而不是 \(h(x)+kx\)。
  

凸性证明

显然 wqs 二分最难的部分在于凸性的证明，其他部分都是套路和板子，以下是常见证明凸性的方法：
<ul>感性理解/打表验证：很多时候在比赛时我们无法或者没有时间证明一个东西的凸性，此时常见的思路是猜测他具有凸性，之后通过感性理解/打表验证的方式非严谨地证明他的凸性。如例题 I。
规约为费用流等凸的问题。如例题 III。
通过 DP 转移方程归纳证明凸性。
交换论证：以最小化问题为例，假设我们现在有了 \(g(x)\) 和 \(g(x+2)\) 的方案构造，此时我们通过交换其中的元素构造出了两个 \(x+1\) 的方案，那么就证明了 \(2g(x+1)\le g(x)+g(x+2)\) 即 \(g(x+1)-g(x)\le g(x+2)-g(x+1)\)，所以函数是下凸的。如例题 IV。
四边形不等式：对于带个数限制的区间分拆问题，朴素 DP 是 \(f(i,j)\) 表示前 \(i\) 个元素划分为 \(j\) 段的答案，转移为 \(f(i,j)=\min_{k\) 第 \(i+1\) 次替换后的增加量，我们可以交换这两次替换。因此最小生成树的边权和是关于白边数量下凸的。</p>点击查看代码[code]int n,m,k,tot,cnt,MST,fa[N];struct Edge{        int u,v,w,col;}E[M];int get(int x){return (x==fa[x])?xfa[x]=get(fa[x]));}int val(Edge x,int mid){        if(x.col) return x.w;        return x.w-mid;}int check(int mid){        sort(E+1,E+m+1,[&](Edge x,Edge y){                if(val(x,mid)==val(y,mid)) return x.col>y.col;                return val(x,mid)