决策单调性_成型笔记

决策单调性

警告：本篇中关于“二维凸性”的描述有误，四边形不等式并不意味着二维凸性，这种性质被称为矩阵的蒙日性，是极为高阶的内容，感兴趣者可以自行搜索。

但这个错误对本篇的应用价值没有损害，在怀疑一个问题有决策单调性时，更多地我们会去观察贡献形式，进而举反例或打表，而不是尝试去证明其满足四边形不等式。

决策单调性是一类统称，根据其名字可以直观感受到优化的思路，即把无用的决策点压缩起来，引起复杂度质的改变。

通常决策单调性体现在一维上（之后也有多维的例子），令 $S$ 表示状态组，$p(i)$ 表示 $f_{S,i}$ 的最优转移点在 $i$ 这一维上的最小/最大数值，我们描述其为：

$$i<j\Rightarrow p(i)\le p(j)$$

决策单调性可以用来优化 $\rm dp$。

注：斜率优化与 $\rm Smawk$ 算法也属于决策单调性范围，但前者有更便利的理解方式，后者绝大多数时候把 $\cal O(n\log n)\to$ 大常数 $\cal O(n)$，所以本文不涉及到这两种算法。

目录：

• 理论：四边形不等式
  • 概述：实质是凸优化
  • 最小后缀问题
  • 区间拆分问题
  • 区间合并问题
• 实现方法：分治
  • 概述：最常用的技巧
  • $\rm trick:$ 贡献难算
  • 例题
• 实现方法：二分队列
  • 概述：在线的决策单调性
  • 例题
• 带个数限制的区间拆分问题
  • 概述：复杂度上的进展
  • 解决方法：$\rm wqs$ 二分 + 决策单调性
  • 例题
• 理论：反四边形不等式
  • 概述：另一种凸优化
• 实现方法：二分栈
  • 概述：优化实现
  • 例题
• 实现方法：线段树分治 + 分治
  • 概述：为何二分栈失去了作用
  • 例题

理论：四边形不等式

概述：实质是凸优化

四边形不等式作为一种优化，绝大多数情况下都是用来判断决策单调性的。

假设 $w(i,j)$ 是一种代价函数，其应用场景在下面我们会提到。

四边形不等式：若 $\forall a\le b\le c\le d,w(a,c)+w(b,d)< w(a,d)+w(b,c)$，则称 $w$ 这个二元函数满足四边形不等式，简记方法是**「交叉优于包含」**。

一些更深的理解（初学可以跳过）

使用更高的视角来看该式，我们可以变形得：

$$w(b,d)-w(a,d)-w(b,c)+w(a,c)\le 0$$

若把 $w$ 写到一个二维平面上，则若 $w$ 是某个二元函数 $g$ 的二维前缀和，该式描述的就是每个子矩形的和都非正，更清楚的描述是每个点上的值都非正。

换句话说就是 $w$ 的二维混合差分 $\Delta_i\Delta_j w$ 在定义域中非正。

但请注意这个“在定义域内”，这并不能理解为这个矩阵的所有元素都非正，如果那样就可以推导出 $a$ 不变 $b$ 越大则 $w(a,b)$ 越小。

实际上取 $w(a,b)=b-a$ 就可以推翻上面的最后一个推导，原因是四边形不等式仅仅描述了一个非正矩形的二维前缀和，而这个“非正矩形”是可以作为一个大矩形的子矩形的！外面的东西不受我们控制，所以四边形不等式没有那般强悍的性质。

想象一下 $w$ 的图像，实际上它应当是一个三维下凸包（$z$ 轴是数值维），它的每个平行于 $z$ 轴的二维截面都是凸函数，而不是一个单调函数。

所以四边形不等式以及反四边形不等式（下凸包变成上凸包，在“二分栈”部分会提到）能够优化的本质其实是二维凸优化。

这可以解释许多 $w$ 的性质，在后文我们会提到。

四边形不等式可以用来判断一些情况下的决策单调性。

最小后缀问题

考虑一类 $\rm dp$：$f_j\xleftarrow[i\le j]\min w(i,j)$，其中 $w(i,j)$ 是一种代价函数（这甚至不能被称作 $\rm dp$，但我们此处仅讨论决策点的关系）。

• 定理：若 $w$ 满足四边形不等式，则 $f$ 满足决策单调性。

证明

$\rm Proof$：使用反证法，我们假设 $c<d$，且 $a=p(d)<p(c)=b$，此时必定满足 $a<b<c<d$，则：

$$\begin{align}w(a,d)&\le w(b,d)\\w(b,c)&\le w(a,c)\end{align}$$

此时 $(1)+(2):w(a,d)+w(b,c)\le w(b,d)+w(a,c)$，前者 $<$ 后者时直接与四边形不等式矛盾，前者 $=$ 后者时取等条件变为 $(1),(2)$ 的取等条件，可知 $a,b$ 都能转移到 $c,d$，没区别，与 $p(c),p(d)$ 的最小/最大性矛盾。

你可能会说怎么会有 $\rm dp$ 式长这样呢，但其实这属于一个中间结论，可以证明满足四边形不等式的 $w(a,b)$ 每维对另一维都有决策单调性。

这在更高维的视角来看其实就是三维凸包的一维 $x(y)$ 增大，数值维 $z$ 对另一维 $y(x)$ 的极值点偏移是单调的。

区间拆分问题

考虑一类 $\rm dp$：$f_j\xleftarrow\min f_i+w(i,j)$（或者 $f_j\xleftarrow\min g_i+w(i,j)$）。

（可以理解为将 $[1,n]$ 拆分为若干区间，每个区间都有代价。）

如果不给任何额外信息，这是一个 1D/1D 动态规划，需要 $\cal O(n^2)$ 的时间复杂度。

• 定理：若 $w$ 满足四边形不等式，则 $f$ 满足决策单调性。

证明

$\rm Proof$：类似上文，假设 $c<d$，且 $a=p(d)<p(c)=b$，此时必定满足 $a<b<c<d$：

$$\begin{align}f_a+w(a,d)&\le f_b+w(b,d)\\f_b+w(b,c)&\le f_a+w(a,c)\end{align}$$

此时 $(1)+(2)$ 也能导出上文的结论。

这个证明也告诉我们，$f(a)+w(a,b)+g(b)$ 和 $w(a,b)$ 是否具有四边形不等式的性质是相同的，证明就是在定义式中 $f,g$ 都消掉了。

之后判断 $w(i,j)$ 是否满足四边形不等式的时候，就可以忽略仅和 $i$ 或者 $j$ 有关的项了。

更深入的理解

这在更高维的视角其实就是把区间拆分成 $w(a,b)+w(b,c)+w(c,d)+\cdots$，考虑任意两个相邻项的合并，其实是 $r=b$ 的一个凸函数与 $l=b$ 的一个凸函数的二维归并，其实质是对第一个凸函数的每个点复制一份第二个凸函数，并整体加上该点的 $y$，这自然得到了一个二维凸函数。

• 对它的证明可以看出，决策单调性不依赖 $f$ 数组，只依赖 $w$ 的四边形不等式性质，换句话说就算我给定 $f$ 的初值不满足任何性质，也可以套用决策单调性。

对 $f_j\xleftarrow\min f_i+w(i,j)$ 的优化是下文将要提到的“二分队列”，对 $f_j\xleftarrow\min g_i+w(i,j)$ 的优化是下文将要提到的“分治”。

区间合并问题

考虑一类 $\rm dp$：$f_{l,r}\xleftarrow\min f_{l,k}+f_{k,r}+w(l,r)$，此时记 $p(l,r)$ 为最优且最小/最大的 $k$。

区间包含单调性：$\forall a\le b\le c\le d,w(b,c)\le w(a,d)$，即小区间优于大区间，其实质是 $w(a,b)$ 关于 $a$ 单减，关于 $b$ 单增。

差分的视角来看就是 $\Delta_i w\le 0,\Delta_jw\ge 0$。

• 引理：若 $w$ 同时满足 区间包含单调性 和 四边形不等式，则 $f_{l,r}$ 也满足四边形不等式。

证明

$\rm Proof$：设 $a\le b\le c\le d$，我们要证 $f(a,c)+f(b,d)\le f(a,d)+f(b,c)$。

令 $e=p(a,d)$，讨论 $e$ 的位置。

1. $e\in[b,c]$。
   • 此时考虑 $E=p(b,c)$ 的位置，下处考虑 $E\le e$，$E>e$ 是对称的，目前字母们的顺序是 $a\le b\le E\le e\le c\le d$：

$$\begin{aligned}f(a,d)+f(b,c)&=[f(a,e)+f(e,d)+w(a,d)]+[f(b,E)+f(E,c)+w(b,c)]\\&= [f(a,e)+f(b,E)]+[f(e,d)+f(E,c)]+[w(a,d)+w(b,c)]\\&\ge [f(a,E)+f(b,e)]+[f(e,d)+f(E,c)]+[w(a,c)+w(b,d)]\\&=[f(a,E)+f(E,c)+w(a,c)]+[f(b,e)+f(e,d)+w(b,d)]\\&\ge f(a,c)+f(b,d)\end{aligned}$$

• • 解释：等号都是拆开或者分组，第一个 $\ge$ 中的第一组是一个归纳假设，即用小区间的四边形不等式证明大区间的四边形不等式。
  • 第二个 $\ge$ 其实就是把两组分别找了两个转移点，必定不优于最优转移点。

2. $e\in[a,b)\cup(c,d]$，假设 $e\in[a,b)$，另一种情况是对称的，目前字母们的顺序是 $a\le e\le b\le c\le d$：

$$\begin{aligned}f(a,d)+f(b,c)&=[f(a,e)+f(e,d)+w(a,d)]+f(b,c)\\&=f(a,e)+[f(e,d)+f(b,c)]+w(a,d)\\&\ge f(a,e)+[f(e,c)+f(b,d)]+w(a,d)\\&= [f(a,e)+f(e,c)+w(a,c)]+f(b,d)\\&\ge f(a,c)+f(b,d)\end{aligned}$$

• • 解释：第一个 $\ge$ 是归纳假设以及区间包含单调性，第二个 $\ge $ 是最优转移点。

证明比结论复杂不少，记住结论就好。

• 定理：若 $f$ 满足四边形不等式，则 $p(l,r-1)\le p(l,r)\le p(l+1,r)$，前后两个区间的长度比该区间少 $1$。

证明

$\rm Proof$：$f(l,k)+f(k,r)+w(l,r)$ 若 $r$ 固定，将参数视为 $(l,k)$，则其满足四边形不等式，因为与 $(l,k)$ 同时有关的项是 $f(l,k)$。

根据“最小后缀问题”部分的推论，我们可以知道 $k$ 对 $l$ 满足决策单调性，也就是 $p(l,r)\le p(l+1,r)$。

类似的，$l$ 固定时 $(k,r)$ 满足四边形不等式，$p(l,r-1)\le p(l,r)$。

有了该结论我们就可以直接记录 $p_{l,r}$，然后利用其优化转移，区间长度相同的每层总枚举次数是 $n$，复杂度 $\cal O(n^2)$，利用该结论你可以通过经典例题：$\cal O(n^2)$ 的石子合并。

在实际应用中，我们几乎完全不关心四边形不等式的成立性，通常打个表验证就可以开始做了，或者蒙一个上去然后拍。

实现方法：分治

概述：最常用的技巧

分治套路通常有一维是层数，每层仅转移到下一层。

每次处理 $[l,r]$ 的时候，区间内的最优转移点必定 $\in[p(l),p(r)]$，我们暴力求出 $p(m=\frac{l+r}{2})$，然后递归，总复杂度 $\cal O(n\log n)$。

void DP(int l,int r,int pl,int pr);

$\rm trick$：贡献难算

如果我们的贡献难以 $\cal O(1)$ 求出，但是能快速移动左右端点，那也可以达到 $\cal O(n\log n)$ 的复杂度，这是一个震撼的结果。

左右端点分开考虑，右端点每次从 $l$ 或 $r$ 跳到 $m=\frac{l+r}2$，左端点每次从 $p(l)$ 或 $p(r)$ 跳到 $p(m)$，移动次数都是区间长级别的，故得证。

（该分析建立在每次还原端点的基础上，实际操作上不还原也不会劣于该算法。）

值得注意的是，类似回滚莫队，该算法也是可以支持端点单调变化的，只需要支持撤销，具体推导类似回滚莫队，略过了（CF1386C）。

例题：P4360 [CEOI2004] 锯木厂选址

数轴上有 $n$ 个点，每个点有位置和权值 $a_i$，还有一个已经确定的在所有点右边的洞，每个点会往右走直到遇到一个洞，此时向答案贡献权值与路程的乘积。

让你再在任意位置添加两个洞，使得答案最小。

$n\le 2\times 10^4$。

显然洞一定修在某一个点脚下。

设状态 $f_{i,k}$ 表示前 $i$ 个点有 $k$ 个洞（只算前 $i$ 个点）的总代价，转移枚举上一个洞在哪，$\cal O(n^2)$，$f_{i,k}\gets f_{j-1,k-1}+w(j,i)$。

我们直接大胆猜测这玩意有决策单调性（这个洞往后移了它前一个洞显然没有理由往前移），开始分治。

快速求 $w(j,i)=\sum_{k=j}^i (x_i-x_k)a_k$，只需要维护区间 $x_ka_k$ 的和还有 $a_k$ 的和即可。

核心代码

#define mid (L+R>>1)
void DP(int L,int R,int pL,int pR) {
    if(L>R) return;
    int pM=pL;f[mid]=w(1,pM-1)+w(pM,mid);
    F(i,pL+1,min(mid,pR)) 
        if(w(1,i-1)+w(i,mid)<=f[mid]) 
            pM=i,f[mid]=w(1,i-1)+w(i,mid);
    DP(L,mid-1,pL,pM);DP(mid+1,R,pM,pR);
}

P4767 [IOI2000] 邮局

数轴上有 $n$ 个村庄，你要放置 $m$ 个邮局，使得村庄到最近邮局的距离和最小。

$n\le 3000,m\le 300$。

顺便提一嘴：只放一个邮局是经典问题，放在中位数上即可，证明可以考虑往左挪一格和往右挪一格答案的变化量。

根据这个经典问题我们知道邮局放在某个村庄上肯定不劣。

$w(l,r)$ 就是 $\frac{x_l+x_r}{2}$ 左边的村庄都去左边的邮局，右边的去右边的邮局，$\mathcal O(\log V)$ 二分出分界点计算即可，计算方法同上题。

复杂度 $\mathcal O(nm\log n\log V)$。

本题村庄坐标很小，可以对每个坐标预处理出比它大的第一个村庄，可以省掉一个 $\log V$。

CF868F Yet Another Minimization Problem

$w(l,r)=\sum_{i<j,i,j\in[l,r]}[a_i=a_j]$，把整个序列拆分成 $k$ 段，求所有段费用和的最小值。

$n\le 10^5,k\le \min(n,20)$。

首先盲猜有决策单调性（这个可以利用四边形不等式交叉优于包含来证），利用上文的 $\rm trick$ 可以求出贡献。

核心代码

void DP(ll g[],ll f[],int L,int R,int pL,int pR) {
    if(L>R) return;
    while(r<mid) A(++r);
    while(l>pL) A(--l);
    while(r>mid) D(r--);
    while(l<pL) D(l++);
    int pM=pL;f[mid]=g[pL-1]+res;
    F(i,pL+1,min(mid,pR)) {
        D(l++);
        if(g[l-1]+res<=f[mid]) pM=i,f[mid]=g[l-1]+res;
    } DP(g,f,L,mid-1,pL,pM);DP(g,f,mid+1,R,pM,pR);
}

CF833B The Bakery

$w(l,r)$ 是区间颜色数，求 $k$ 段价值和的最大值。

$n\le 35000,k\le 50$。

前面是同一个数越来越多则贡献爆炸增长，求总贡献最小，这里是同一个数第二次出现就没贡献，求总贡献最大。

同理可得本题也有决策单调性，跟上题一样做即可。

P5574 [CmdOI2019] 任务分配问题

$w(l,r)$ 是区间顺序对数，求 $k$ 段价值和的最小值。

$n\le 25000,k\le25$。

这种题你就要想如果你是一个大胖段，你把左右元素扔给左右的段会不会让全局答案少很多，显然是会的。

所以可以感性理解到决策单调性。

HDU2829 Lawrence

$w(l,r)=\sum_{i,j\in[l,r],i<j}a_ia_j$，求 $k$ 段价值和的最小值。

$n,k\le 10^3$。

不难发现交叉优于包含，决策单调性即可。

CF1603D Artistic Partition *3000

$w(l,r)=\sum_{i,j\in[l,r],i\le j}[\gcd(i,j)\ge l]$，把 $[1,n]$ 分成 $k$ 段，每段非空，求 $k$ 段价值和的最小值。

$T\le 3\times 10^5,1\le k\le n\le 10^5,\rm 3\ seconds$。

按照套路首先盲猜 $w$ 满足四边形不等式。

神级结论：若 $n<2^k$，则令第 $i$ 段为 $[2^{i-1},2^i)$，这样每段任意不同两数的 $\gcd$ 都 $<2^{i-1}$，答案为 $n$，达到了理论最优。

然后 $k$ 就变成 $\cal O(\log n)$ 了。

倘若我们对每个前缀求出一个数组 $f_{i,k}$，表示前 $i$ 个人分成 $k$ 段的总价值，则我们可以快速回答询问，这是一个 soft 1D/1D 动态规划。

现在的问题就是快速计算 $w(l,r)$。

我们看一下能否莫反，令 $x/y=[\frac xy]$：

$$\begin{aligned}\sum_{i=l}^r\sum_{j=i}^r[(i,j)\ge l]&=\sum_{k=l}^{r}\sum_{i=1}^{r/k}\sum_{j=i}^{r/k}[(i,j)=1]\\&=\sum_{k=l}^r\sum_{i=1}^{r/k}\varphi(i)\\&=\sum_{k=l}^r{\rm S}\varphi(r/k)\end{aligned}$$

这是一个整除分块的形式，可以 $\cal O(\sqrt r)$ 计算，那你总复杂度就是 $\cal O(n\sqrt n\log^2 n)$，还是很恐怖的。

我们可以对每个 $r$ 预处理出根号段相等数列，记录每段那些相等元素的值，记录后缀和，然后就可以 $\cal O(1)$ 查询了。

复杂度 $\cal O(n\sqrt n+n\log^2 n)$。

CF321E Ciel and Gondolas

$w(l,r)=\sum_{i<j,i,j\in[l,r]}a_{i,j}$，求分 $k$ 段代价和最小。

$n\le4000,k\le \min(n,800),a_{i,j}\ge 0$。

先证一下决策单调性：交叉或包含时中间那块的元素都可以与本身贡献两次，与两边贡献一次。

但交叉时两边元素不能互相贡献，包含时可以，故交叉优于包含。

预处理 $w(l,r)$，跑决策单调性，复杂度 $\cal O(nk\log n+n^2)$。

P4072 [SDOI2016] 征途

将 $n$ 段不能分割的路合并成 $m$ 段，使方差最小，输出方差 $\times \ m^2$。

$n\le 3000$。

化简一下发现其实输出的是 $m\sum x^2-(\sum x)^2$。

后面一项是已知的，只需要令前面那项最小即可。

$w(l,r)=(\sum_{i=l}^ra_i)^2$，这一看就很凸。

P3515 [POI2011] Lightning Conductor

给定一个长度为 $n$ 的序列 $\{a_n\}$，对于每个 $i\in [1,n]$ ，求出一个最小的非负整数 $p$ ，使得 $\forall j\in[1,n]$，都有 $a_j\le a_i+p-\sqrt{|i-j|}$

$1 \le n \le 5\times 10^{5}$，$0 \le a_i \le 10^{9}$ 。

把式子变形：$p_i=\max_j(a_j+\sqrt{|i-j|})-a_i$，我们正反做一遍，把 $\sqrt {|i-j}$ 变成 $\sqrt {i-j}$，显然 $\sqrt{i-j}$ 是凸的，所以把 $a$ 视为原来的 $\rm dp$ 数组进行一次决策单调性转移即可，分治就可以解决。

需要注意的细节

很烦，决策单调性涉及到小数的时候必须要用浮点类型存，否则函数的凸性并不能保证。

最后的时候再取整。

沙东省集2024 D2T1

给定一个序列，对每个 $k\in[0,n]$ 求出取反至多 $k$ 个元素最大的最大前缀和是多少。

$n\le2\times 10^5$。

这个东西并不是凸的，也不是增量构造的。

考虑 $k$ 对最终选择的前缀是具有决策单调性的，即 $k$ 增大，最终选择的前缀必定不会减少。

确定前缀我们只需要反转绝对值最大的几个负数即可，这可以用主席树实现。

然后套上分治即可。

实现方法：二分队列

概述：在线的决策单调性

二分队列是（半）在线版本的决策单调性，相对的讲，分治是离线版本的决策单调性，二者的适用范围没有其他区别。

我们可以优化四边形不等式中提到的这个问题：$f_j\xleftarrow\min f_i+w(i,j),i<j\Rightarrow p(i)\le p(j)$。

具体来说，我们维护一个单调队列，每个元素都是一个三元组 $(l,r,p)$，表示 $[l,r]$ 的目前的最优决策点都相等，是 $p$。

• 初始时该队列中仅有 $(1,n,1)$，我们枚举 $k=(2\to n)$ 作为决策点插入进队列中。
• 当插入决策点 $k$ 时，我们首先将它与队尾 $(l,n,p)$ 进行比较，若 $k$ 决策 $l$ 比 $p$ 还优秀，那 $p$ 肯定没用了，可以弹出队尾。
• 重复上述过程直到有一个决策点与他各有千秋，谁也不能完全代替谁，则把该决策点插进队尾，接下来我们需要求出两个人的 决策分界点，在 $w$ 好求的前提下，这可以使用二分来求出。

由于决策点是从小到大插入的，故我们比较两个决策点的时候二者的贡献皆已确定。

上面这类 $\rm dp$ 的决策点贡献需要依赖 $f$，故需要边求决策点边更新 $f$，下面的口胡题是另一类不需要依赖 $f$ 也不应当更新 $f$ 的题目。

上面这种实现方法可以见下面例题的“核心代码”。

口胡题中使用了二分队列的另外一种实现方式，与二分栈十分相似，我们在二分栈部分介绍。

例题：P1912 [NOI2009] 诗人小G

给定 $n$ 个串，分成若干段，每个串不能切开，两个在同一段的串中间要加一个字符，给定 $L,P$，使 $\sum |x-L|^P$ 最小。并构造方案。

$n\le 10^5,T\le 5,P\le 10$。

其实就是 $w(l,r)=|\sum_{i=l}^r a_i+r-l-L|^P$，令 $a_i\gets a_i+1,L\gets L+1$ 就是 $w(l,r)=|\sum_{i=l}^ra_i-L|^P$。

然后 $f_{j}\gets f_{i-1}+w(i,j)$，求 $\min f_n$。

二分队列板题。

需要注意的细节

本题答案超过 $10^{18}$ 时无需输出，但实际存储上我们不应将超过 $10^{18}$ 的量统一用 $\infty$ 存储，这会导致决策单调性无法比较两个值的大小关系。

正确的做法是使用 long double，它的精度足以表示 $[1,10^{18}]\cap \mathbb N$。

还有就是本题是严格判等，字符串不要多输出空格和换行。

核心代码

ld val(int l,int r) {
    return f[l]+w(l,r);
}
main:
q[hd=tl=1]={1,n,0};
F(i,1,n) {
    while(hd<tl&&q[hd].r<i) ++hd;f[i]=val(pos[i]=q[hd].p,i);
    while(hd<tl&&val(i,q[tl].l)<=val(q[tl].p,q[tl].l)) --tl;
    int L=q[tl].l,R=n,mid,ans=n+1;
    while(L<=R) mid=L+R>>1,val(i,mid)<=val(q[tl].p,mid)?R=mid-1,ans=mid:(L=mid+1);
    if(ans<=n) q[tl].r=ans-1,q[++tl]={ans,n,i};
} 

这里的结构体写法也可以变成队列中仅记录决策点，然后对每个决策点维护决策范围两个数组，是一样的。

口胡题

给定一个有向正权图，定义路径的权值 $d(e_1,e_2,e_3,\dots)=\sum_iw(e_i,e_{i+1})$，其中 $w(a,b)$ 是能快速计算的关于 $a,b$ 的单增凸函数，例如 $w(a,b)=\sum_{i=0}^5a^ib^{5-i}$。

求 $1$ 到每个点的最短路。

$n\le 2\times 10^5$。

看到这个条件我们第一反应肯定是把边当作点跑最短路，但那显然规模无法接受。

但我们知道长得像最短路的问题通常只能用最短路算法来做，所以我们顺着往下想。

每条边现在都有一个二元组 $(d_i,w_i)$，表示最短路和边权，你发现这可以决策单调性，将每个点出点按照 $w$ 从小到大排序，则决策点必定 $d$ 单调不升，$w$ 单调不降（因为两个大一点的 $w$ 就可以爆炸增长）。

用我们更熟悉的语言来表述：将决策点按 $d$ 从小到大排序，则交叉优于包含。

你发现 $\rm dijkstra$ 的过程正好就是把 $d$ 从小到大确定的，于是我们在每个点维护入点对出点的决策单调性，对每条边维护它的决策范围。

每条边要维护目前更新到决策范围中的哪条出边了，这条出边出队之后该点需要更新下一条出边，即下文代码中的 upd()。

核心代码

const int N=2e5+5;vector<int> G[N],q[N];
ll a[N],b[N],c[N],d[N],Z[N],ans[N];int n,m,k,X[N],Y[N],st[N],ed[N],vis[N];
struct S {
    ll d;int x,pre;S(ll d=0,int x=0,int pre=0):d(d),x(x),pre(pre) {} 
    bool operator<(S y)const{return d>y.d;}
};priority_queue<S> Q;
int fd(int x,int y) {//d[x]<d[y],Z[x]>Z[y],y第一个决策点 
    int v=Y[x],L=0,R=sz(G[v])-1,mid;
    while(L<=R) mid=L+R>>1,d[x]+w(Z[x],Z[G[v][mid]])>=d[y]+w(Z[y],Z[G[v][mid]])?R=mid-1:(L=mid+1);
    return L;
}
void psh(int x) {//把x这条边加到出点的决策区间 
    int y=Y[x];auto &q=::q[y];
    if(sz(q)&&Z[q.back()]<=Z[x]) return st[x]=1,ed[x]=0,void();
    while(sz(q)>1&&fd(q.back(),x)<=fd(q[sz(q)-2],q.back())) st[q.back()]=ed[q.back()]+1,q.pop_back();
    if(sz(q)) st[x]=fd(q.back(),x),ed[q.back()]=st[x]-1;
    else st[x]=0;ed[x]=sz(G[y])-1;q.pb(x);
}
void upd(int x) {//更新“下一条”x这条边的出点的出边
    if(st[x]>ed[x]) return;int y=G[Y[x]][st[x]];
    d[y]=min(d[y],d[x]+w(Z[x],Z[y]));
    Q.push(d[y],y,x),st[x]++;
}
int main() {freopen("path.in","r",stdin);freopen("path.out","w",stdout);
    n=read();m=read();k=read();
    F(i,1,k) a[i]=read(),b[i]=read(),c[i]=read();
    F(i,1,m) {
        X[i]=read();Y[i]=read();Z[i]=read();
        G[X[i]].pb(i);
    } F(i,1,n) sort(begin(G[i]),end(G[i]),[](int x,int y){return Z[x]<Z[y];}); 
    memset(ans,0x3f,sizeof ans);memset(d,0x3f,sizeof d);
    for(int x:G[1]) Q.push(d[x]=0,x,0);F(i,1,m) st[i]=1;
    while(!Q.empty()) {
        auto x=Q.top();Q.pop();
        if(x.pre) upd(x.pre);
        if(vis[x.x]) continue;vis[x.x]=1;
        psh(x.x);upd(x.x);
    } F(i,1,m) ans[Y[i]]=min(ans[Y[i]],d[i]);
    F(i,2,n) printf("%lld\n",ans[i]>1e18?-1ll:ans[i]);
    return 0;
}

带个数限制的区间拆分问题

概述：复杂度上的进展

在上文的例题中，我们见到了很多这种把长为 $n$ 的序列拆成 $k$ 段的问题。

将其形式化描述，设 $f_{i,k}$ 表示 $[1,i]$ 分为 $k$ 段的最小代价，则有转移方程：

$$\begin{cases}f_{0,0}=0\\f_{i,0}=f_{0,k}=\infty&i,k>0\\f_{i,k}=\min_j\{f_{j,k-1}+w(j,i)\}&i,k>0\end{cases}$$

我们在之前的例题中都是用 $\cal O(nk\log n)$ 的复杂度处理的。

看到这个问题形式我们就想到了 $\rm wqs$ 二分，那能否将二者联系起来呢？

有一个用不到的结论，类似上文的区间合并问题：

$$p(i,k-1)\le p(i,k)\le p(i+1,k)$$

解决方法：$\rm wqs$ 二分 + 决策单调性

很重要的结论：若 $w(l,r)$ 满足四边形不等式，则 $f_{n,k}$ 关于 $k$ 是凸的。

证明

只需证明 $f_{n,k-1}+f_{n,k+1}\ge 2f_{n,k}$ 即可。

考虑 $f_{n,k-1}$ 分成了 $k-1$ 段，而 $f_{n,k+1}$ 分成了 $k+1$ 段，那么在前一种分段方式中必然存在一段中有两个后者的分段点，将后半部分的第二种与前半部分第一种组合，就得到了两个 $k$ 段的方案，类似上面的形式使用四边形不等式证明后者必定优于前者即可。

所以 $f_{j,k}\gets f_{i,k-1}+w(i,j)$ 变成了 $f_{j}\gets f_{i}+w(j,i)+C$，利用上文的套路解决即可。

上文所有的固定段数 $\rm dp$ 都可以这么做，复杂度 $\mathcal O(n\log n\log V)$。

注意到这是一个半在线决策单调性，所以要使用二分队列。

例题：P6246 [IOI2000] 邮局 加强版

套用上面非加强版的思路，换成二分队列写法即可。

前面所有的 $k$ 段划分问题都可以利用该方法实现。

丑陋的核心代码

struct X {
    int l,r,p;
} q[N];
struct V {
    ll f;int k;
    V operator+(ll x) {return {f+x,k};}
    V operator|(ll x) {return {f+x,k+1};}
    bool operator<=(V b) {return f==b.f?k<=b.k:f<=b.f;}
} f[N];
auto ck=[](ll val) {
    q[hd=tl=1]={1,n,0};
    auto cal=[&](int i,int j)->V {return f[i]+w(i,j)|val;}; 
    F(i,1,n) {
        while(q[hd].r<i) ++hd;f[i]=cal(q[hd].p,i);
        while(hd<=tl&&cal(i,q[tl].l)<=cal(q[tl].p,q[tl].l)) --tl;
        if(hd>tl) {q[++tl]={1,n,i};continue;}
        int L=i,R=n,mid,ans=n+1;
        while(L<=R) mid=L+R>>1,cal(i,mid)<=cal(q[tl].p,mid)?R=mid-1,ans=mid:(L=mid+1);
        if(ans<=n) q[tl].r=ans-1,q[++tl]={ans,n,i};
    } V ans={(ll)1e18,0};
    F(i,1,n) {
        auto v=f[i]+((s[n]-s[i-1])-(n-i+1)*a[i]);
        if(v<=ans) ans=v;
    } return ans;
};
ll L=-1e9,R=1e9,mid,ans;
while(L<=R) ck(mid=(L+R)/2).k<=m?R=mid-1,ans=mid:(L=mid+1);
cout<<ck(ans).f-ans*m<<endl;

理论：反四边形不等式

概述：另一种凸优化

仍然考虑该式：$f_j\xleftarrow\min f_i+w(i,j)$。

若此时 $w$ 满足**「包含优于交叉」**，即反向的四边形不等式，那么不难发现：设 $p(i)=s$，则 $\forall j>i,p(j)\notin(s,i)$。

形象地表述这一结论：一个最优转移点的出现可以**「支配」所有比它大的候选转移点**，或者说弹掉它们。

需要注意的是：由于不断地有新的候选转移点加入，所有点的最优转移点并没有决策单调性，既不单增也不单减。

实际上反四边形不等式优化是另一种形式的凸优化，由于它凸的方向与优的方向并不一致，形成的转移并没有那么显然的决策单调性，但仍然可以在一定程度上优化。

实现方法：二分栈

概述：优化实现

二分栈可以解决 无转移范围限制（每个点都可以转移到之后的每个点） 的 反四边形不等式优化。

事实上二分栈并不是决策单调性，但与二分队列很像，用来启发一下思路。

• 有很多题解声称自己使用了二分栈，但其中有从栈底使用元素的情况，那实际上就是二分队列。

我们可以用栈来实现反四边形不等式的优化过程，每次取出栈顶用来转移，加入转移点时比较它与栈顶的决策分界点 $p$ 和栈顶与次栈顶的决策分界点 $q$，若 $p\le q$ 那么栈顶被该转移点和次栈顶支配，可以弹出。

Q：为何不能直接用单调栈来实现？每次到了新点就反复弹栈直到栈顶优于次栈顶，被弹掉的元素之后一定不会有用。

A：这主要是因为 次栈顶优于栈顶 的时间可能晚于 次次栈顶优于次栈顶 的时间，如果当前应该用次次栈顶，但你却仍然判断栈顶优于次栈顶，不去弹栈，这就爆了。

这里可以二分决策分界点的理论支撑就是**「包含优于交叉」**，虽然没有决策单调性，但对于两个决策点来说，左边的点总是会决策靠右边的一段区间，以及两点之间的这段区间。

把二分的边界设置妥当就可以排除掉后者的干扰，然后二分出分界点。

• 二分栈的重点是左边界的设立，需要找到一个对 $i,j$ 都合法的左端开始二分。

代码实现

$f_j\gets f_{i-1}+w(i,j),p(j)=i$（这种情况下 $w(i,j)$ 算的是 $[i,j]$ 贡献，可以有 $p(i)=i$）写法：

#define sz(x) int(x.size())
#define tp s.back()
#define se s[sz(s)-2]
vector<int> s;
int cal(int i,int j) {return f[i-1]+w(i,j);}//i<=j
int pos(int i,int j) {
    int L=j,R=n,mid,ans=n+1;
    while(L<=R) mid=L+R>>1,cal(i,mid)<cal(j,mid)?R=mid-1,ans=mid:(L=mid+1);//此处小于是优于
    return ans;
}//i<j，pos(i,j) 及之后 i 更优秀，严格之前是 j 优秀
F(i,1,n) {
    while(sz(s)>1&&chk(se,tp)<=chk(tp,i)) s.pop_back();
    s.push_back(i);
    if(sz(s)>1&&chk(se,i)<=i) s.pop_back();//全方位打不过原来的栈顶
    f[i]=val(tp,i);
}

$f_j\gets f_i+w(i,j),p(i)=i$（$w$ 算的是 $(i,j]$ 的贡献，这种情况下 $p(i)<i$）写法：

#define sz(x) int(x.size())
#define tp s.back()
#define se s[sz(s)-2]
vector<int> s;
int cal(int i,int j) {return f[i]+w(i,j);}//i<=j
int pos(int i,int j) {
    int L=j+1/*改动*/,R=n,mid,ans=n+1;
    while(L<=R) mid=L+R>>1,cal(i,mid)<cal(j,mid)?R=mid-1,ans=mid:(L=mid+1);//此处小于是优于
    return ans;
}//i<j，pos(i,j) 及之后 i 更优秀，严格之前是 j 优秀
s.push_back(0);/*改动*/
F(i,1,n) {
    f[i]=val(tp,i);/*改动*/
    while(sz(s)>1&&chk(se,tp)<=chk(tp,i)) s.pop_back();
    s.push_back(i);
    if(sz(s)>1&&chk(se,i)<=i+1/*改动*/) s.pop_back();//全方位打不过原来的栈顶
}

后者更适合算前缀和相减的时候用，更简洁一点。

看了这个实现你会发现，二分队列其实可以用相同的写法写淘汰的那部分，唯一区别是转移点从队首掏出来而不是队尾（栈顶）。

例题：P5504 [JSOI2011] 柠檬

给定序列，每个元素有颜色 $c$，$w(l,r)=\max_c(c\cdot {\rm cnt}_{c,[l,r]}^2)$，求分成任意段的最多价值。

$n\le 10^5$。

用转移式 $f_j\gets f_{i-1}+w(i,j)$，首先可以猜到 $c_i=c_j$，否则不优，这是一定的。

然后我们把每个颜色的子序列拿出来，贡献就变成了 $w(l',r')=c\cdot (r'-l'+1)^2$，这显然是个下凸函数，而我们求最大值，于是包含优于交叉。

• 反四边形不等式与四边形不等式的使用条件类似，只需要贡献函数满足性质，原数组可以是任意数组。

那我们把每个颜色拿出来，内部都满足二分栈的使用条件，于是我们每个颜色建立一个栈转移即可。

注意我们加入转移点仍然是枚举 $1\to n$，因为转移要依赖的 $f_{i-1}$ 并不一定是该颜色。

核心代码

int n,p[N],c[N],bn[N];ll f[N];
vector<int> s[N];
ll cal(int i,int j) {
    assert(c[i]==c[j]);
    return f[i-1]+1ll*c[i]*(p[j]-p[i]+1)*(p[j]-p[i]+1);
}
int pos(int i,int j) {
    assert(c[i]==c[j]);
    int c=::c[i],L=p[j],R=bn[c],mid,ans=R+1;
    auto w=[&](int l,int r) {return 1ll*c*(r-l+1)*(r-l+1);};
    while(L<=R) mid=L+R>>1,f[i-1]+w(p[i],mid)>=f[j-1]+w(p[j],mid)?R=mid-1,ans=mid:(L=mid+1);
    return ans;
}
int main() {
    F(i,1,n=read()) p[i]=++bn[c[i]=read()];
    F(i,1,n) {
        auto &s=::s[c[i]];
        #define tp s.back()
        #define se s[sz(s)-2]
        while(sz(s)>=2&&pos(se,tp)<=pos(tp,i)) s.pop_back();
        s.push_back(i);
        if(sz(s)>=2&&pos(se,i)<=p[i]) s.pop_back();
        f[i]=cal(tp,i);
    } cout<<f[n]<<endl;
    return 0;
}

实现方法：线段树分治 + 分治

概述：为何二分栈失去了作用

我们会遇到这样一类问题：满足反四边形不等式，但每个点能转移到的区间范围有限。

此时我们回看反四边形不等式的推导过程：加入一个点可以**「支配」所有比它大的候选转移点**，而比他大的候选转移点有可能在转移区间上比其优秀，于是并不能直接弹掉，我们陷入了两难境地。

于是，我们不得不花费一个 $\log$ 的代价，将每个点加入到线段树上它的决策区间上，然后对于每个区间我们进行新的反四边形不等式优化即可。

注意到现在的问题被大大简化：连每个点必须转移到它之后这个限制都没了，我们发现转移真正拥有了 「反决策单调性」，$i<j\Rightarrow p(i)\ge p(j)$，且问题已经变成了离线版本，我们可以直接 分治 解决。

需要特别注意的是，各个线段树端点的问题是独立的，需要临时构建 $\rm dp$ 变量，不要依赖 $\rm dp$ 数组中的值，否则无法保证决策单调性。

复杂度 $\cal O(n\log^2 n)$（因为分治的复杂度是关于区间长度成线性对数关系）。

代码实现

void mo(int l,int r,int x,int L,int R,int d) {
    if(R<l||r<L) return;if(l<=L&&R<=r) return c[d]+=x,void();
    mo(l,r,x,L,mid,l(d));mo(l,r,x,mid+1,R,r(d));
}
void dp(vec &c,int L,int R,int pL,int pR) {
    if(L>R) return;
    int pM=pL,res=f[c[pL]]+w(c[pL],mid);
    F(i,pL+1,pR) if(f[c[i]]+w(c[i],mid)<=res) res=f[c[i]]+w(c[i],mid),pM=i;
    f[mid]=min(f[mid],res);
    dp(c,L,mid-1,pM,pR);dp(c,mid+1,R,pL,pM);
}
void go(int L,int R,int d) {
    if(sz(c[d])) dp(c[d],L,R,0,sz(c[d])-1),c[d].clear();
    go(v,L,mid,l(d));go(v,mid+1,R,r(d));
}

例题：P5244 [USACO19FEB] Mowing Mischief P

$T\times T$ 网格图上 $n$ 个格点是特殊点，你需要找一条 $(0,0)$ 到 $(T,T)$ 的路径，使得只能往右往上走，经过尽可能多的特殊点的前提下，使相邻两个特殊点间的面积和最小，输出这个面积和。

保证没有点同行或同列，$x_i,y_i\in[1,T-1]$。

$T\le 10^6,n\le 2\times 10^5$。

由于没有点同行或同列，所以你可以将本题抽象成一个长为 $n$ （或者长为 $T$）的序列，经过尽可能多的特殊点就是某个最长上升子序列。

可以对每个点求出它是最长上升子序列的哪一层（以其为结尾的最长上升子序列长度），这样我们就可以限定它从比它小的一层转移过来。

有结论是同一层的点是单调不增的，否则就可以跑到下一层。

画个图我们可以发现两层之间的转移满足包含优于交叉，于是我们瞪眼一看，发现事情并不简单，转移必须满足 $x_i<x_j\wedge y_i<y_j$，这是一个区间，于是我们可以线段树分治 + 分治解决。

核心代码

void mo(int x,int v) {
    if(!x) return c[0]=v,void();
    for(;x<=T;x+=x&-x) c[x]=max(c[x],v);
}
int q(int x) {int res=c[0];
    for(;x;x&=x-1) res=max(res,c[x]);
    return res;
}
ll w(int i,int j) {
    if(x[i]>x[j]||y[i]>y[j]) return 1e13;
    return 1ll*(x[j]-x[i])*(y[j]-y[i]);
}
#define mid (L+R>>1)
#define l(x) (x<<1)
#define r(x) (x<<1|1)
void mo(vec &v,int i,int L,int R,int d) {
    if(x[i]>x[v[R]]||y[i]>y[v[L]]) return;
    if(x[i]<=x[v[L]]&&y[i]<=y[v[R]]) return o[d]+=i,void();
    mo(v,i,L,mid,l(d));mo(v,i,mid+1,R,r(d));
}
void dp(vec &u,vec &v,int L,int R,int pL,int pR) {
    if(L>R) return;
    int pM=pL;ll res=f[u[pL]]+w(u[pL],v[mid]);
    F(i,pL+1,pR) if(f[u[i]]+w(u[i],v[mid])<=res) res=f[u[i]]+w(u[i],v[mid]),pM=i;
    f[v[mid]]=min(f[v[mid]],res);
    dp(u,v,L,mid-1,pM,pR);dp(u,v,mid+1,R,pL,pM);
}
void go(vec &v,int L,int R,int d) {
    if(sz(o[d])) dp(o[d],v,L,R,0,sz(o[d])-1),o[d].clear();
    if(L==R) return;
    go(v,L,mid,l(d));go(v,mid+1,R,r(d));
}
auto DP=[](auto &&u,auto &&v) {
    for(int i:u) mo(v,i,0,sz(v)-1,1);
    go(v,0,sz(v)-1,1);
};
int main() {
    n=read();T=read();
    F(i,1,n) {
        id[x[i]=read()]=i;
        y[i]=read();
    } id[0]=++n,x[n]=y[n]=0;id[T]=++n;x[n]=y[n]=T;
    F(i,0,T) if(id[i]) {
        int u=q(y[id[i]])+1;
        mo(y[id[i]],u);
        if(sz(v[u])) assert(y[v[u].back()]>=y[id[i]]);
        v[u]+=id[i];
    } memset(f,0x3f,sizeof f);f[n-1]=0;
    F(i,2,n) {
        DP(v[i-1],v[i]);
        if(!sz(v[i+1])) {
            ll ans=1e18;
            for(int x:v[i]) ans=min(ans,f[x]);
            cout<<ans<<endl;return 0;
        }
    } 
    return 0;
}

参考资料

Liuxizai：决策单调性优化 dp 学习笔记

command_block：DP的决策单调性优化总结

Alex_Wei：DP 优化方法大杂烩 II.

OI Wiki：四边形不等式优化