四边形不等式

四边形不等式ψ(｀∇´)ψ

对于一个二维序列 \(f\)，如果它满足：

\[ \forall a \le b \le c \le d, f(a, c) + f(b, d) \le f(a, d) + f(b, c) \]

那么称 \(f\) 满足四边形不等式，也可以记作相交不大于包含。

一个更特殊一点的判定是：

\[ \forall a < b, f(a, b) + f(a + 1, b + 1) \le f(a, b + 1) + f(a + 1, b) \]

并且这是 \(f\) 满足四边形不等式的充要条件，之后的一些问题也会用到它。

一些比较常见的满足四边形不等式的 \(f\)：

区间和 \(k\) 次方和（\(val \in \mathbb{N}\)）
区间逆序对个数（通常会结合类莫队算法）

优化一类区间 dpψ(｀∇´)ψ

对于区间 dp 当中的合并型问题，我们有以下方程：

\[ dp(l, r) = \min\limits_{k = l}^{r - 1}\{dp(l, k) + dp(k + 1, r)\} + w(l, r) \]

引理：如果 \(w\) 满足四边形不等式且满足 \(\forall l \le u \le v \le r, w(u, v) \le w(l, r)\)，那么 \(dp\) 也满足四边形不等式。

这个证明省略，需要的读者可以自行查阅或者证明。

因为 \(dp\) 满足四边形不等式，那么可以推出一个结论：

结论：设 \(m(l, r)\) 表示使 \(dp(l, r)\) 取到最小值的 \(k\)，那么有 \(m(l, r - 1) \le m(l, r) \le m(l + 1, r), (l + 1 < r)\)。

这个证明省略，需要的读者可以自行查阅或者证明。

因为这一类区间 dp 转移依赖的阶段是区间，那么换句话说 \(m(l, r - 1), m(l + 1, r)\) 早就已经在上个阶段计算好了。

所以我们在当前层枚举 \(k\) 的时候就只需要枚举 \((m(l + 1, r) - m(l, r - 1))\) 次了！

总体复杂度就从 \(O(n^3)\) 降到了 \(O(n^2)\)。

优化一类分割型 dpψ(｀∇´)ψ

在区间 dp那篇博客里我们提到过，分割型 dp 有两种：

要求恰好分 \(x\) 段
没有要求恰好分多少段

前一种的 dp 是：\(dp(i, j)\) 表示考虑前 \(i\) 个位置，分了 \(j\) 段的答案，那么转移就是 \(dp(i, j) \gets dp(k, j - 1) + w(k + 1, i), (k < i)\)。

后一种则是：\(dp(i)\) 表示考虑前 \(i\) 个位置分若干段的答案，转移就是 \(dp(i) \gets dp(j) + w(j + 1, i), (j < i)\)。

不妨将这两种方程统一成 \(dp(i) = \min\limits_{j < i}\{f(j) + g(j + 1, i)\}\) 的形式，其中 \(f\) 可以是 \(dp\) 也可以不是。

换句话说我们认为这两种情况的区别是，前一种是以分割段数为阶段，分层转移的，后者则是同层转移的。

但是它们都有一个结论：

如果 \(w\) 满足四边形不等式，那么会有：

\(dp\) 的最优决策点单调不降，不管是 \(\min\) 还是 \(\max\)。

这个证明省略，需要的读者可以自行查阅或者证明。

那么对于第一种情况，我们可以考虑分治来解决这个问题。

具体来说，设 \(\text{solve}(l, r, u, v)\) 表示只处理 \([l, r]\) 间的转移且决策点在 \([u, v]\)，然后每次找到 \(mid\) 的最优决策点 \(t\)，利用决策单调性引理递归做 \(\text{solve}(l, mid, u, t), \text{solve}(mid + 1, r, t, v)\)。

代码类似这样（从 OI wiki 贺的）：

Code

int n;
long long C(int i, int j);
vector<long long> dp_before(n), dp_cur(n);

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  pair<long long, int> best = {INF, -1};
  for (int k = optl; k <= min(mid, optr); k++) {
    best = min(best, {dp_before[k] + C(k, mid), k});
  }
  dp_cur[mid] = best.first;
  int opt = best.second;
  compute(l, mid - 1, optl, opt);
  compute(mid + 1, r, opt, optr);
}

然后对于第二种情况，形如 \(dp(i) = \min\limits_{j < i}\{dp(j) + w(j + 1, i)\}\) 的转移，只能确定这样的东西：

对于一对 \(a < b\)，\(dp(b)\) 的最优决策点一定不小于 \(dp(a)\) 的最优决策点，但是如果最优决策点都是 \(1\) 那就卡到 \(O(n^2)\)了。

所以没法分治，除非转移里面只有一个 \(w\) 没有 \(dp\)，这样一次分治才可以做。

但是有一种解决方法，我们再在外层套一个分治，对于一个 \([l, r]\)，我们先分治算 \([l, mid]\) 的 dp，算完之后在考虑对从 \([l, mid] \to [mid + 1, r]\) 的转移做决策单调性分治，此时相当于是强制分层转移了，会多一个 \(\log\)。

但是常数非常小，只要出题人疏忽了，评测姬快一点基本就过了。

当然还有一种解决方式，考虑用单调栈/队列来做这个部分。

具体来说我们维护一个三元组集合 \((pos, l, r)\) 表示 \(pos\) 这个点目前是 \([l, r]\) 中的最优决策点。

然后就是，考虑计算 \(dp(i)\)，首先考虑队头，如果 \(\text{head}.l \le i \le \text{head}.r\) 那么令 \(\text{head}.l = i\)，否则如果不包含那么就弹出 \(\text{head}\)。

然后转移直接取队头，考虑插入 \((i, ..., ...)\) 这个三元组。

每次考虑对于 \(\text{tail}.l\) 这个位置，看看是 \(i\) 更优还是 \(\text{tail}.l\) 更优，如果 \(i\) 更优就弹出 \(\text{tail}\)，否则说明 \(i\) 对应的 \(l\) 应该在 \(\text{tail}.l\) 之后，因为有单调性所以考虑二分这个位置 \(x\)。

然后把队尾的三元组的 \(r\) 改成 \(x - 1\)，插入 \((i, x, n)\) 即可。

性质ψ(｀∇´)ψ

这部分是为了对一些不太常见的函数分析。

我比较懒就摘抄 OI-wiki 了。

性质 1：若函数 \(w_1(l,r),w_2(l,r)\) 均满足四边形不等式（或区间包含单调性），则对于任意 \(c_1,c_2\geq 0\)，函数 \(c_1w_1+c_2w_2\) 也满足四边形不等式（或区间包含单调性）。

性质 2：若存在函数 \(f(x),g(x)\) 使得 \(w(l,r) = f(r)-g(l)\)，则函数 \(w\) 满足四边形恒等式。当函数 \(f,g\) 单调增加时，函数 \(w\) 还满足区间包含单调性。

性质 3：设 \(h(x)\) 是一个单调增加的凸函数，若函数 \(w(l,r)\) 满足四边形不等式并且对区间包含关系具有单调性，则复合函数 \(h(w(l,r))\) 也满足四边形不等式和区间包含单调性。

性质 4：设 \(h(x)\) 是一个凸函数，若函数 \(w(l,r)\) 满足四边形恒等式并且对区间包含关系具有单调性，则复合函数 \(h(w(l,r))\) 也满足四边形不等式。

首先需要澄清一点，凸函数（Convex Function）的定义在国内教材中有分歧，此处的凸函数指的是（可微的）下凸函数，即一阶导数单调增加的函数。

四边形不等式