王钦石二分优化

Vision271 · 2022-07-18 17:54:11 · 个人记录

概述

• wqs 二分通常用于解决形如“选 m 个”或“分 m 段”问题。

• 该类问题的朴素 DP 状态往往形如“考虑了前几个，已经选了几个/分了几个”，导致状态数起步为 n^2。

• wqs 二分通过将该类 DP 考虑完毕所有点时的 dp_n 视作一个平面直角坐标系下的函数凸壳，不断使用直线切该凸壳以二分出一个恰当的斜率，从而确保切到 x=m 的点并以此求出答案。

• upd：思维不要太死板，wqs 不一定是用来优化 DP 的。不日将会把它从 DP 优化搬出去，大概会和整体二分一起开一个新专题。

实现原理

引入

• 考虑一个板题：

• 给你一个数列 a_n，现要求你将其分为 m 段，使得 \sum\limits_{i=1}^m sum_{l_i\sim r_i}^2 取得最小值。

分析

• 首先我们肯定会一个暴力 dp：

  • 定义 \mathit{dp}_ {i,j} 为考虑了前 i 个数字，已经分成了 j 段所能获得的最小值。
  • 初始化：\mathit{dp}_ {i,1}=sum_{1\sim i}^2。
  • 状态转移方程：\mathit{dp}_ {i,j}=\min(\mathit{dp}_ {k,j-1}+sum_{k+1\sim i}^2)(k<i)。

• 状态数 n* m，转移 O(n)，不可接受。

• 我会斜率优化！

  • 把每个“选了多少个”视为一层，每一层开一个单调队列。O(n* m)。
  • 可惜的是复杂度仍然不可接受。

• 考虑找性质降维（n 这一维显然不可降，那就不是 dp 了，根本没有过程）。

• 以当前分成了几段为 x 轴，总共的最小总代价（dp_n）为 y 轴，建立平面直角坐标系（下图对应的是 a=1,2,1,2 的情况，因为我不会调整几何画板的比例尺只好缩放了一下线段）。

• 可以看到，其具备一定的单调性（在本题中为单调不增），构成了一个凸包（本题中为下凸包）。

• 显而易见，我们所求的答案就是 x=m 时这个凸包上的点的纵坐标。但问题就在于我们无法快速求出——但是我们知道它的形状和单调性。

• 考虑用直线去切这个下凸包（注意这个直线没有定点，我们就让它靠到这个图像上就好了）。能够看出，当斜率的绝对值不断增大，切到的位置也就不断向左上移动；反之亦然。

• 从而如果我们能够得到一个斜率 k，使得对应直线恰好切该凸包于 x=m 处，就有希望较方便地求出答案。

• 那问题就转化成了怎么求这个 k。

  • 观察图像容易发现，随着 k 改变，切到的点是单调的，所以可以二分。
  • 观察这张网图（侵删），可以看出一个有益的性质：恰好为切线的那一条有最小/最大的 y 轴截距（其实也可以转化成 x 轴截距，但没必要）（在这张网图里面是最大，在我的图里是最小）（有的 wqs 二分图是像此图一样会拐的）。

• 稍微运用一点高中解析几何知识，记切线的 y 轴截距为 f(k)，记切点的横坐标为 x_0，我们有 \mathit{dp}_ {n,x_0}=k* x_0+f(k)（即 y=kx+b）。

• 由此，如果我们能求出点 (m,\mathit{dp}_ {n,m}) 对应切线的 k，我们就可以 O(1) 地求出最优答案。

• 稍微变换一下：f(k)=\mathit{dp}_ {n,x_0}-x_0* k。

• 诶？我怎么觉得这个式子暗示我们 f(k) 与 x 无关？

• 考虑一下啊，我们既然是二分了 k，那我们就得想办法整一个 O(n) 的 check。

• 铛铛！回想一下我们这样的目的是什么：降维！

• 直接去掉“恰好选 m 个”的限制，我们来一遍暴力的斜优 dp ！

  • 具体来讲，就是 dp_i 表示考虑完前 i 个分了任意段的最大/小截距。
  • 方程：dp_i=\min(dp_j+sum_{j+1\sim i}^2-K)。即每分一段对应的点在凸包上就右移一个，从而对应的截距就减一个 K（不减 K 的就是原始 dp 方程了）。顺便记录一下 dp_n 是分了几段。
  • 从而我们知道有当前 K 时最优解为 dp_n 对应段数，需要注意的是可能切到了一条线而非一个点，即有一个“截距最小段数集”。

• 如果 m 在这个“截距最小段数集”，那么说明我们的 K 终于二分到站了。直接输出答案就好。

• 如果不在，容易求出最小段数集在 m 的哪边。以本题为例，如果是在左边，那么我们就可以增大斜率（减小斜率的绝对值）来尝试向右走。

• 最后说一下为什么我们要把 K 作为整数二分：

  • 只要确保切到对应点且对应点对应截距最大，我们其实不关心 K 到底是多少。
  • 容易证明，凸包上相邻两点的连线截距必然为整数（\Delta x 一定为整数），且当我们的直线与其重合时，必然不可能有该连线（当然可能是多点共线而非二点共线）之外的点截距更小。
  • 所以我们只要最后让 K 切到一条线就行了，从而整数二分。
  • 由于最后要输出的答案一定是整数，实数二分很可能出精度问题。

• upd：一个小扩展——选 \geqslant/\leqslant m 个。

  • 我会三分（因为这个凸壳不一定是半凸壳，可能拐的）！
    • 三分成恰选 m 个。O(n\log m\log K)。
  • 我会带悔贪心！
    • 一边去你！
  • 我会讨论峰/谷值对应的 x。
    • 把 K 先搞成 0，于是我们一定切到峰/谷点，从而可以得到对应的 x。
    • 于是就是两个半凸壳了，两者分别单调，若 m 跨了拐点一定是恰选拐点处最优，否则一定是选 m 最优。
    • 例题：\text{P1484 种树}。其实隔壁那个环上的也能做，但是不要难为 wqs 二分了（得写破环成链 DP），用点带悔贪心吧...（人家带悔贪心的链表可以循环，来者不拒）

例题

P4983 忘情

• 题意：a_n 分 m 段，使得（化简后，毕竟我们不是来讲怎么推式子的）\sum\limits_{i=1}^m (sum_{l_i\sim r_i}+1)^2 取得最小值。

• 数据范围：n,m\leqslant 10^5，0<x_i\leqslant 1000。

• 水题，我来切！

• 随便手推两下很容易看出，分的段数越多越小。画一下凸包就和我的图差不多。

• 我们倍增二分一个 K（k 用于斜优），每次 check(K-step)。

• upd：这种写法好像常数大，所以可以以细节多一点为代价只跑一个。大体来讲就是两种思路，一种是找不合法的最后一个然后 ++，例如尽量小然后必须严格大于；另一种是找到最后一个合法的，例如尽量大然后大于等于（这两个的背景都是上半凸壳）。

• 判一下。

  • 如果上界比 m 小，说明切到了左上方的点，K 太小了，走过头了，return 0，不能减。
  • 如果下界比 m 大，那就是在右下方，K太大了（注意这里都是带符号讨论），必须减。
  • 如果两个都不是说明已经切到我们要的 m 了，直接用截距算出 ans 输出然后 exit(0) 。
  • 如果多组询问可以用 flag，或者 return 一个 pair，反正随心意整两下咋都行。

• 反正我觉得倍增写起来舒服。以及果然一切二分能做的倍增二分都能做，就连三分也可以求导来做。倍增二分，暂时滴神！

ABC218H

• 题意：共 n 个球排成一列，选出 m 个染成蓝色，其余为红色。如果 c_i\neq c_{i+1}，那么获得 v_i 的收益。求最大收益。

• 数据范围：1\leqslant m<n\leqslant 2\times 10^5,v\leqslant 10^9。

• 唔。这个东西...首先上来暴力 dp，dp_{i,j} 表示考虑了前 i 个染了 j 个，哦还得挂个 0/1 辅助维记录上一个是啥。

• 容易猜想到 dp_n 是一个上凸包，如果它拐弯了那就是 m\geqslant \dfrac{n}{2}，此时把颜色反转一下就好。

• 于是是个板子...二分 K 去截它，具体来讲，dp_i 表示考虑前 i 个染了任意个的最大截距。

• 于是有 dp_i=\max(dp_{i-1},dp_{i-2}+v_{i-1}+v_{i-2}-K)。

• 其余略。

CF739E

• 参见“贪心”。