浅谈决策单调性

Hootime · 2026-03-06 08:59:03 · 算法·理论

好难。Hootime 是不是不适合学 OI。

以下的 \mathrm{opt}(i) 表示位置 i 的最优决策点，\mathrm{opt}_j(i) 表示只考虑起始点到 j 的情况下 i 的最优决策点。

从四边形不等式讲起

四边形不等式

若无特殊说明，以下均保证 a \le b \le c \le d。

是一个不等式（废话），长这样：

其中 a \le b \le c \le d。

这个东西还有另一种形式：

简记为「交叉小于包含」。

下证两个式子等价。

充分性很容易证明，只需要将代入 a' = a, b' = a+1, c' = b, d' = b+1 代入 (1) 即可。

必要性：

我们将 (2) 改写为如下形式：

w(a+1, c+1)-w(a+1, c) \le w(a, c+1)-w(a, c) \tag{1.1}

那么我们使用数学归纳法，假设 w(b-1, c+1)-w(b-1, c) \le w(a, c+1)-w(a, c)

由 (1.1) 得，w(b, c+1)-w(b, c) \le w(b-1, c+1)-w(b-1, c)

合并两式，得

w(b, c+1)-w(b, c) \le w(a, c+1)-w(a, c) \tag{1.2}

又改写 (1.2) 得：

w(b, c+1)-w(a, c+1) \le w(b, c)-w(a, c) \tag{1.3}

我们再次使用数学归纳法，假设 w(b, d-1)-w(a, d-1) \le w(b, c)-w(a, c)

那么同理，可得：

w(b, d)-w(a, d) \le w(b, c)-w(a, c) \tag{1.4}

移项得：

w(a, c)+w(b, d) \le w(a, d)+w(b, c)

不严谨地说如果你的大脑比较擅长空间想象的话，由 w(a+1, b+1)-w(a+1, b) \le w(a, b+1)-w(a, b) 和 w(a+1, b+1)-w(a, b+1) \le w(a+1, b)-w(a, b) 可得满足四边形不等式的函数在两个维度上的二阶混合差分都是非正的。换句话说，固定其中任意一维，另一位的差分都是非正的。

经典结论

1

对于问题：f_i = \min_{1 \le j \le i} w(j, i)，如果 w 满足四边形不等式且 i < i'，有 \mathrm{opt}(i) \le \mathrm {opt}(i')。

下证性质的正确性。

反证法。设存在 i < i' 且 \mathrm{opt}(i) > \mathrm {opt}(i')。

设 j \leftarrow \mathrm{opt}(i), j' \leftarrow \mathrm {opt}(i')。整理如上不等关系得 j' < j \le i < i'。

又由最优性可得，w(j, i) < w(j', i), w(j', i') < w(j, i')。

将两式相加得 w(j, i)+w(j', i') < w(j', i)+w(j, i')，即 w(j', i)+w(j, i') > w(j, i)+w(j', i')。

我们用 a, b, c, d 代替 j', j, i, i'，发现式子变成了 w(a, c)+w(b, d) > w(a, d)+w(b, c)，与四边形不等式矛盾。

2

对于问题：f(i) = \min_{1 \le j \le i} f(j-1) + w(j, i)，如果 w 满足四边形不等式且 i < i'，有 \mathrm{opt}(i) \le \mathrm {opt}(i')。

下证性质的正确性。感谢 @Jink 给我讲懂了这个证明。

引理：如果 w 满足四边形不等式且 i < i+1，有 \mathrm{opt}(i) \le \mathrm {opt}(i+1)。

设 j \leftarrow \mathrm{opt}(i), k \in [1, j-1]。

由于 j 最优，有：

f_{j-1}+w(j, i) \le f_{k-1}+w(k, i) \tag{2.1}

移项得：

f_{j-1}-f_{k-1} \le w(k, i)-w(j, i) \tag{2.2}

又由于 w 满足四边形不等式，有 w(k, i)+w(j, i+1) \le w(j, i) + w(k, i+1)。移项得：

w(k, i)-w(j, i) \le w(k, i+1)-w(j, i+1) \tag{2.3}

合并 (2.2)，(2.3) 得：

f_{j-1}-f_{k-1} \le w(k, i+1)-w(j, i+1) \tag{2.4}

移项得：

f_{j-1}+w(j, i+1) \le f_{k-1}+w(k, i+1) \tag{2.5}

从而证明了此时选 k 一定不优于选 j，因此 \mathrm {opt}(i+1) \notin [1, j-1]。

对这个结论使用数学归纳法可以得到决策单调性，这里就不赘述了。

算法们

拿到决策单调性其实题就做了一大半了。剩下的就是选择算法并且实现。

选择算法主要需要看 w 的性质。w(i, j) 能直接 \mathrm O(1) 计算那当然是极好的，但是很多情况下 w 的性质没有这么好。有以下两种比较常见的性质：

• 移动访问：有点像莫队。具体就是 w(i, j) 只能通过 w(i \pm 1, j) 或者 w(i, j \pm 1) 来 \mathrm O(1) 求得。
• 动态计算：w(i, j) 的计算依赖 f_{1 \sim i}，你只能顺次计算 f 和 i。

这两个性质并不互斥，有可能同时出现。

整体二分

假设我们现在要处理 [L, R] 的 \mathrm{opt}(i)，已知 \mathrm{opt}(i) \in [l, r]。

我们算出 [L, R] 的区间中点 mid，并且暴力求得 \mathrm{opt}(mid)。由于决策单调，我们知道了 \forall i \in [L, mid-1], \mathrm{opt}(i) \in [l, \mathrm{opt}(mid)], \forall i \in [mid+1, R], \mathrm{opt}(i) \in [\mathrm{opt}(mid), r]。

于是我们对两边分治一下即可。考虑分治树，树高为 \log n，每层我们总共花费了 \mathrm O(n) 暴力求出了 \mathrm{opt}(mid)，于是时间复杂度为 \mathrm O(n \log n)。

整体二分是可以处理移动访问的情况的（先把 r 移动到 mid，再顺次移动 l），但是由于需要先计算 \mathrm {opt}(mid)，所以不能做动态计算。

如果要处理动态计算的话当然可以使用 cdq 分治，但是 \mathrm O(n \log^2 n) 明显不是很优，可以使用后面提到的简化 LARSCH 算法。

二分队列

我们换一个思路，考虑当前及以前的决策对之后的决策的影响。

我们加强【经典结论 1】的结论。

对于问题：f(i) = \min_{1 \le j \le i} w(j, i)，只考虑 1 \le j \le k 的决策，如果 w 满足四边形不等式且 i < i'，有 \mathrm{opt}_k(i) \le \mathrm {opt}_k(i')。

换句话说就是如果只考虑 1 \le j \le k 的决策，那么仍然有决策单调性。

下证加强结论的正确性。

我们有 w'(j, i) = w(j, i)+M[j > k]，其中 M 为充分大的正实数。我们发现 w' 仍然满足四边形不等式。

这时我们考虑问题 f'(i) = \min_{1 \le j \le i} w'(j, i)。由【经典结论 1】可得该问题的决策单调性。明显在该问题中大于 k 的决策是不优的，于是我们得到 \mathrm{opt}'(i) = \mathrm{opt}'_k(i) = \mathrm{opt}_k(i)，结论得证。

那么我们就可以对已有的决策 k \in [1, j]，对于将来的决策 k' \in (j, n]，我们可以用一个队列存下来 [1, k] 的每一个决策及其在 (k, n] 为最优决策的区间，这些区间并起来应该为 (k, n] 并且不交。

这么讲可能有点抽象，下面是算法流程。可以适当类比斜率优化中的单调队列。

• 我们正在处理决策 j。如果我们发现队列的队头的最优区间的右端点是 j-1，那么把它弹掉。其实不弹问题也不大来着，但是会多一次二分加大常数。
• 然后我们要把 j 入队。如果你想问为什么不是先处理 f_j 再入队那么问题有 w(j, j) 的转移。
  • 我们设队尾元素为 j'，其最优区间的左端点为 l_{j'}，右端点为 r_{j'}。
  • 如果决策 j 在 l_{j'} 优于 j'，那么 j' 可以完全被 j 代替，因而没有存在的必要了，我们弹掉 j'。重复这个过程直到没有能被弹掉的 j'。
  • 如果队列空了，我们向队列中加入 (j, j, n)，表示认为 j 是之后所有决策的最优决策点。
  • 否则，我们在当前的队尾的最优区间 [l_{j'}, r_{j'}] 中二分出一个位置 p，满足 p 是第一个 j 优于 j' 的位置。然后，我们将队尾修改为 (j', l_{j'}, p-1)，再向队列中加入 (j, p, n)。特别地，如果二分出 p > n，那么 j 在整个区间上都不优，不用入队。
• 然后我们发现队头就是 j 的最优决策，更新 j 即可。

每个决策都只会被入队和出队一次，出队是 \mathrm{O}(1) 的，入队是 \mathrm{O}(\log n) 的，因而时间复杂度为 \mathrm{O}(n \log n)。

这个算法很明显可以处理动态计算的问题，但是处理不了移动访问。

简易 LARSCH 算法

这个算法可以看 Register_int 大佬的在线决策单调性地皮还能单老哥分治做？ - 洛谷专栏。讲得还是很好的。

这个算法其实可以部分类比 CDQ 分治，有点像又不是很像的样子。

我们设计一个函数 \mathrm{solve}(l, r)，作用是算出 f_{l \sim r}。这里按照 Hootime 的习惯使用了闭区间。