[misc-1]wqs 二分的一种特殊处理方式

Moeebius · 2024-01-12 14:15:22 · 科技·工程

通过整数二分实现 wqs 二分时的一个细节是凸壳上存在三点共线的情况。

一种广为人知的处理方案为：我们每次二分时，跑出「分组」方案最多的解，也就是所有切点中横坐标最大的一个；如果这个横坐标大于等于要求的 k，那么调大斜率，否则调小。

很遗憾，这种方法并不完美。

• 我们没法求出具体方案，只能求出答案。
• 对于高维情况无法方便处理。

如果我们只想要求出具体方案，对于大多数的问题（DP 过程中凸性仍满足），我们可以采用如下处理：

我们发现 DP 过程中可以转移过来的位置是凸壳上一段连续的区间。维护 L_i, R_i 分别表示第 i 个位置最优方案下，最少、最多分成多少组；转移时顺带更新即可。

这样我们已经可以非常优雅地实现二分了：

while (l <= r) {
  auto mid = (l + r) >> 1;
  check(mid);
  if (L[n] <= k && R[n] >= k) {
    ans = mid;
    break;
  } else if (L[n] > k)
    l = mid + 1;
  else
    r = mid - 1;
}

输出答案时，我们倒着扫一遍，记当前还需要分 cur 组，上一个确定的分段点为 x，我们找到编号最大的，满足 cur \in [L_i, R_i] \land fi + \text{cost}(i, x)=f_x 的 i，将其加入分段点即可。

il void construct() {
  vector<int> sol;
  k--;
  for (int l = n - 1, r = n; l; l--) {
    if (L[l] <= k && R[l] >= k && calc(l, r) + ans == f[r]) { // ans 是斜率
      k--, sol.emplace_back(l);
      r = l;
    }
  }
  reverse(sol.begin(), sol.end());
  cout << "Yes\n";
  for (int x : sol)
    cout << x << ' ';
}

例题-Gym102268J

注意维护 L, R 时略有细节。

另外如果只要求答案但是高维还有一种处理方案：对于上凸的函数 f(x)，令 g(k)=\max_{x}{f(x)-kx}+ka 是下凸的，并且最小值恰好为 f(a)。

直接二分即可。