决策单调性听课笔记
ty_mxzhn
·
·
算法·理论
讲课人：jiangly，讲评来源：代码源。
这只是我的笔记。如果侵权致歉。
各种神秘矩阵
- 单调矩阵：每行最小值位置单调的矩阵。
- 完全单调矩阵：任取一个子矩阵（任意行任意列的交点）都单调的矩阵。
- 蒙日矩阵：满足四边形不等式（交叉优于包含）的矩阵。
单调矩阵 \subset 完全单调矩阵 \subset 蒙日矩阵。
三种决策单调性相关算法
分治法
调用 Solve(l,r,L,R)，每次找到 m=\dfrac{l+r}{2}。花费 O(R-L) 的时间找到决策点 p。
调用 Solve(l,m-1,L,p),Solve(m+1,r,p,R) 即可。
局限性：只能离线。（可以 CDQ 把在线转离线但会多只 \log）
优点：很好写，只要是单调矩阵就可以做。
单调栈二分（重要）
要求在线，每次加入一列。
考虑之前每一行的当前决策点，二分第一个后面优于前面的位置然后更新。
优点：可以在线。
局限性：难写，需要完全单调性。
SMAWK 算法
咕咕咕。
大致思路是，把偶数行的答案求出以后，奇数行可以在 O(n+m) 的时间复杂度内解决。此时时间复杂度为 O(n+m\log n)。
考虑优化。有一个重要的性质就是如果我们考虑决策单调性的二分算法的话，如果不要二分，当一整列被偏序时直接扔掉它，最后的矩阵会变成 n\times n 的。
于是在分治过程中每递归一下就处理一次刚才的优化就可以做到 O(\min(n,m)) 的时间复杂度。非常厉害。
优点：时间复杂度快。
局限性：很难写，需要完全单调性。
第一组例题
LOJ6039
求 $1\sim k$ 承载力背包价值。
$n\le 10^6,w_i \le 300,k\le 50000$。
设 $f_{c,i}$ 表示考虑了重量 $1\sim c$ 的物品，当前总重量 $i$ 的价值。
$\displaystyle f_{c,ci+b}=\max_{j\le i} f_{c-1,cj+b}+w_{c,i-j}$。
注意到 $w$ 上凸。~~则 $f$ 上凸。~~
~~转移形式形如 $\displaystyle c_{k}=\max_{i+j=k} a_i+b_j$，因为是上凸的所以可以直接 $(\max,+)$ 卷积。复杂度线性。~~
但是有决策单调性做法。$W_{i,j}=w_{c,i-j}$ 满足四边形不等式（蒙日矩阵）则可以使用前文提到的分治法或单调栈二分。卡卡常可能能过。
### GYM102586B
题意懒得抄下来了。大概就是村里第 $i$ 个位置有 $a_i$ 个避难所，每次 $l\sim r$ 要被砸了，一个人要么躲避难所要么出去，有 $S$ 个人在同一个未知的村庄。问最坏情况要走多少步才能躲过去。
考虑答案为要走一步的人数加上要走两步的人数加上要走三步的人一直加下去。
假设走 $d+1$ 步可以走完则答案为：
$$
\sum_{i=0}^dS-\sum_{j=k-i}^{k+i}a_i
$$
可以预处理 $d$ 则对于位置确定情况答案可以 $O(1)$ 计算。
对于一个固定的 $l$ 移动 $r$，前半部分不会变化，而后半部分需要处理。如果我们定义 $f(i,r)$ 表示对于一个 $r$ 村民位置为 $i$ 的代价，则注意到 $f(i,r+1)-f(i,r) \le f(i+1,r+1)-f(i+1,r)$ 于是 $f(i,r)$ 可以被认为是蒙日矩阵（满足四边形不等式）。
把 $l \sim r$ 分裂然后放到线段树的结点上。查询时询问 $\displaystyle \max_{l\le i\le r} f(i,r)$。挂上去以后离线利用线段树结构进行决策单调性分治即可。
# 蒙日矩阵最短路
顾名思义，邻接矩阵为蒙日矩阵的图上的最短路问题。很多情况下没有 $i>j$ 的边。
对于划分问题，可以看成最短路。
一种问题形如，恰好要走 $k$ 条边的最短路。
暴力 Bellman-Ford 可以达到 $O(nk)$ 的复杂度。你可以猜这是凸的直接上 wqs。接下来尝试证明。
因为要证明凸。所以要 $2f(k) \le f(k-1)+f(k+1)$。现在有两种方案，分别是 $k-1,k+1$ 时的方案记为 $A,B$。
把 $B$ 方案的路径和 $A$ 方案的路径用编号交错拼起来。现在要分成两半，两半 $B$ 的个数恰好比 $A$ 的个数多 $1$。
构造两条路径，先在前一半跟着 $A$ 走，后一半跟着 $B$ 走，第二条走刚才没走的。我们试图证明，一定可以找到一条满足条件的路径。
首先证明一定存在可以分成两半的点：考虑此时相当于一条折线走路，问你存不存在一条经过一条直线的点而且不是通过触碰走到而是穿过，这是简单的。
走边不同的地方只有分成两半的位置要证明不等式，直接使用四边形不等式说明。
# wqs 二分（略）
适用范围：凸的就行。
目标：求 $f(k)$。但是不能直接求。
考虑拿一条直线去切这个凸函数。观察切点的位置，（下凸）如果切点在左边则把直线往右转否则往左转即可。
注意：当求切点时有可能有多个切点，请取最左边的。
# 第二组例题
### QOJ9737
打怪，一个怪有 $a_i$ 的经验。现在把怪分成若干个区间一个区间给一个角色打，一个角色会升级，从 $i-1\to i$ 要花 $b_i$ 经验，$b$ 单调。
最大化 $l-c$ 的和，$l$ 是角色等级。
给 $b$ 做前缀和，显然是凸的。设计 $f_i$ 表示前 $i$ 个怪答案。
$$
f_{i}=\max_{j<i} f_j+w(a_i-a_j)-c
$$
$w$ 是分段函数，考虑直接把它用线段连在一起变成上凸的，外面再套一个下取整函数。
比较 $f_{j_1}+w(a_i-a_{j_1})$ 和 $f_{j_1}+w(a_i-a_{j_1})$。为了方便使用之前的结论，考虑直接存储值域。
也即：不再考虑 $a_i -a_j$ 的不连续性。而看成茫茫数轴上的 $n$ 个点。继续套用单调栈二分做法即可。
### 逆序对划分
给大小为 $n$ 的排列划分成 $k$ 段，最小化每段逆序对数量之和。数据范围先不管。
考虑莫队，但是其实这个莫队没有根号。现在我们有一个分治区间，类似整体二分的思路，走的时候其实只带一只 $\log$。
CDQ 一只，莫队一只，二分一只，树状数组一只。四只 $\log$。
### ABC383G
题意：有 $k$ 长度的块，选 $i$ 个不交的块求覆盖数和最大值。对 $1\le i\le \lfloor \dfrac{n}{k}\rfloor$ 求答案。$n \le 2\times 10^5,k\le 5$。
考虑动态规划，把剩余位置计入状态。考虑形式幂级数的形式，可以完美的表示动态规划的状态。不过写成矩阵也行。
考虑分治。思考分治乘形式幂级数，如何使用 $(\max,+)$ 卷积快速合起来。
这本质上是简单的。复杂度可以做到 $O(nk^3\log n)$ 或者 $O(nk^2\log n)$。
# 第三组例题
### 极差划分（GYM103202L）
给大小为 $n$ 的排列划分成 $k$ 段，最大化每段极差之和。对 $k=1\sim n$ 求答案。数据范围 $1\le n\le 10^5$。
极差显然满足四边形不等式。套用上一题结论即可做到单 $\log$。
注意到极差的划分可以看做两端点的绝对值，则分治时两边也是凸的，卷起来即可。
[其他题解指路](https://www.cnblogs.com/apjifengc/p/17041194.html)。
### QOJ2211
一个长度为 $L$ 的环上有 $n$ 个人，设立 $k$ 个邮局，最小化每个人离他距离最近邮局之和。
数据范围：$1\le k \le n \le 2\times 10^5,L\le 10^{12}$。
环先不管。排序后，相当于分 $k$ 段，每次选中位数建立邮局。
是否满足四边形不等式呢？容易证明也是满足的。
还有另一种方法。考虑两个邮局之间的一段，左边往左走右边往右走。也容易证明满足四边形不等式。
第二种方法并不方便，考虑第一种。如果是链直接实现可以做到 $O(n\log n)$ 复杂度。
考虑环。直接断点其实不太现实，因为你断开的方案太多了。
刚才证明凸性的时候说了，把方案 $A$ 和方案 $B$ 放在一起。
如果我们把方案 $X$ 在一边拓展变成 $A$ 另一边拓展变成 $B$ 则有 $2X \ge A+B$ 所以是凸的。
据此有衍生结论，决策点单调。我们发现我们算完一次以后，决策点被分离开来，变成了离线的决策单调性。
对于已经确定了一个点的时候，走出一条路径的时间复杂度是 $O(n\log n)$。据此用类似分治的方法，通过起点分裂到 $k$ 个决策单调性的区间。
一开始求出 $k$ 个区间，最短的那个 $\le \dfrac{n}{k}$，从其中开始分治，则这一部分时间复杂度为 $O(n)$。
[个人荐题](https://www.luogu.com.cn/problem/CF1842I)。
# 第四组例题
### GYM103102A
有 $n$ 列土，第 $i$ 列 $1$ 米价值 $p_i$ 可正可负。
现在要挖土，相邻两列高度差不超过 $1$，请最大化挖土价值和。
数据范围：$n\le 2.5\times 10^5$。
$f_{i,j}$ 表示第 $i$ 个土挖了 $j$ 米，前 $i$ 个土的答案。
$f_{i,j}=\max(f_{i-1,j-1},f_{i-1,j},f_{i-1,j+1})+jp_i
等价于与 (-1,0)(0,0)(1,0) 做闵可夫斯基和再加直线，显然还是凸的。
第一种操作：顶部平台扩大，处理边界。
第二种操作，斜率整体增加一个数。
直接维护 dp 数组的凸包，用一个堆即可。
这其实就是 slope trick。
一个题单。
CF1787H
在 $t$ 时刻交 $i$ 题可以获得 $\max(b_i-k_i t,a_i)$ 的分数。
最大化分数，数据范围：$n\le 2\times 10^5$。
套路的，对于使用 $a_i$ 这一项的题目最后提交，对于需要 $b_i-k_it$ 这一项的题目按照 $k_i$ 从大到小的顺序交。
$f_{i,j}$ 表示前 $i$ 道题交了 $j$ 道题的分数。
$$
f_{i,j}=\max(f_{i-1,j}+a_i,f_{i-1,j-1}+b_i-k_ij)
$$
猜测 dp 数组是凸的。两种操作：
1. 原地加上 $a_i$。
2. 往右边移动一位并加上一条直线。
要取 $\max$ 所以不一定是凸的。接下来是妙妙操作。
$$
f_{i,j}+\dfrac{k_ij(j+1)}{2}=\max(f_{i-1,j}+a_i,f_{i-1,j-1}+b_i-k_ij)+\dfrac{k_ij(j+1)}{2}
$$
$$
f_{i,j}+\dfrac{k_ij(j+1)}{2}=\max(f_{i-1,j}+a_i+\dfrac{k_ij(j+1)}{2},f_{i-1,j-1}+b_i+\dfrac{k_ij(j-1)}{2})
$$
变为 $f_j=\max(f_j+a_i,f_{j-1}+b_i)$ 这样的萌萌函数。但是 $f_j$ 会随着 $k_i$ 的减小而减去一些 $\dfrac{j(j+1)}{2}$。这个其实就是凸的。
还是考虑维护斜率。一操作相当于插入一个 $b_i-a_i$，二操作对每个斜率的影响不是很简单。相当于把第 $i$ 大的数减去 $i$。
拿一颗平衡树打标记即可。时间复杂度 $O(n\log n)$。
### CF1534G
有 $n$ 个点 $(x_i,y_i)$，你在 $(0,0)$ 出发并向上向右走，如果你在 $(X,Y)$ 可以花 $\max(|X-x_i|,|Y-y_i|)$ 的代价激活 $i$。
问你激活每个点的最小代价。
注意到一定在 $x+y=x'+y'$ 这条斜线上激活。
$f_{s,x}$ 表示 $s=x+y$ 的直线现在在 $x$ 而 $<s$ 的线激活完了。
一种是直接往右走，另一种是加上一个绝对值函数。
一种是最小值带着右边走或者左边 $-1$ 右边 $+1$。
可能可以通过奇怪数据结构维护。但是我们考虑维护二阶导数。再维护一下最小值的位置。
第一个操作是把二阶导往右边走。第二个操作是插入两个点，调整一个虚拟点从右边和左边。
用对顶堆维护最小值的两半。时间复杂度 $O(n\log n)$。
# 第五组例题
### QOJ8392
$n$ 个怪，打败 $i$ 要先花 $a_i$ 再赚 $b_i$ 体力。体力始终非负。
对于 $k=1\sim n$ 问一开始最少要多少体力才能打败恰好 $k$ 个怪。
套路的考虑假设确定了打哪些怪要怎么打。显然先打 $a_i<b_i$ 的赚钱怪再打 $a_i \ge b_i$ 的花钱怪。
赚钱怪按照 $a$ 从小到大打，花钱怪按照 $b$ 从大到小打。请注意这里说的是这些怪都要打完的情况。
先打赚钱怪，则我们肯定从左往右使劲打。但是花钱怪不一样。以下先从花钱怪开始考虑。
$f_{i,j}$ 表示 $i$ 怪之后打了 $j$ 个怪的最少初始能量。
$f_{i,j}=\min(f_{i+1,j},\max(0,f_{i+1,j-1}-b_i)+a_i)
dp 数组，<b_i 的部分取 0，\ge b_i 的部分取后一项。因为 b_i 越来越大所以继续往前打怪不优则已经确定。把已经确定的扔掉除了边界处有贡献。
强行认为已经确定的部分答案是 b_i。用优先队列维护后方一段的斜率。
GYM104128H
一颗 n 个点边带权的树边权非负。
选 k 个不同的点并最大化两两距离之和。
数据范围：2\le k\le n\le 10^5。
一个说法是 $f_{x,i}=f_{y,i}+wi(k-i)$。
在树上启发式合并维护闵和即可。时间复杂度 $O(n\log^2 n)$。