决策单调性+斜率优化+wqs二分优化dp
xiaoyang222
·
·
算法·理论
主要是因为网上的 wqs 二分文章有点太难懂了（起码对于我），连带着斜率优化和决策单调性一起讲了，顺便梳理一下这几天的学习。
凸包/斜率优化。
定义凸包：平面上一些点，能将这些点包围起来的最小凸多边形称为凸包。
假设你会凸包。不会的也别急，很好理解的。
“凸”其实就是间距尽量小的时候的差分数组单调。比如 y=x^2+3x-2 就是凸函数（上凸），y=-x^2+3x-2 也是凸函数（下凸），y=\dfrac{1}{x}(x>0) 不是，y=\dfrac{1}{x}(x<0) 是。
不妨变化标准形式（A 和 B 和 D 都是来自 i 的系数，C 可以理解为转移方程的 f，x_j 和 y_j 都可以看作和 j 相关的数，可以是任意数，也可以是和 C 相关的）：
注意这里直接提出来可能会把运算符改变。
这玩意是不是像直线解析式？后面的 $\min$ 中就是直线的交点（也就是截距）（$b=y-kx$）。那么每个点可以转换为 $(x_j,y_j)$，斜率就是 $-\dfrac{A_i}{B_i}$。
由于凸包将所有点都给包起来了，所以最优决策点肯定是在这个凸包的边缘去到。我相信你们是会凸包的。
不同的场景对应不同的实现：
1. 用平衡树维护凸壳．那么寻找决策点的二分操作就转化为在平衡树上二分，插入决策点就转化为在平衡树上插入一个结点，并删除若干个被踢出凸壳的点．此方法思路简洁但实现繁琐（来自 OI-wiki）。此时你可以做任何问题（可以区间查询）。（我不会，见谅 /bq）
2. 使用 CDQ 分治（按时间分治）。先将分治的前半部分的 dp 算出来，再建立凸包，接着对于 $[mid+1..r]$ 的，去二分截距切凸包。二分做法：以上凸壳为例，二分答案，以 $k$ 为斜率经过 $mid$ 点的截距与 $mid-1$ 的截距做差分，判断正负以来判断实在这个峰的哪里。
3. 如果 $x$ 具有单调性，可以直接维护一个单调栈，然后做二分。二分同上。
4. 如果 $x$ 和 $k$ 都有单调性，那么可以维护单调栈，在 3 的基础上可以发现最优点是一直向右边移的，所以可以维护一个指针表示最优取值。
决策单调性只能做到 $\log$，但是有的时候可以用特殊的 4 情况，可以做到线性，会在最终的大汇总例题见到。
可以先拿 [P3195 玩具装箱](https://www.luogu.com.cn/problem/P3195) 练练手（其实这个题的 $k$ 和 $x$ 已经是单调递增的了，可以用 4 写法写写做到线性，也可以用其他的练练手）。代码很简单吧。题解区自认为够了。
---
wqs 二分。
它可以节约状态数。通常是将 $f(i,j)$ 优化成 $g(j)$ 的，同时复杂度也大大降低（通常是 $O(nm)\to O(n\log V)$，这里 $i$ 是 $n$ 量，$j$ 是 $m$ 量）。但是可惜的是他的条件很苛刻。
举个例子：最大多区间和。
> 给你一个长度为 $n$ 的序列 $a$，$a$ 可正可负，你要选出恰好 $m$ 个不相交和包含的区间（这里可以将“恰好”做到“至多”），使得这些区间的数的加和尽量大。（把 $n$ 和 $m$ 看作同阶）（这里由于还没讲决策单调性，将 $O(n \log n \log V)$ 的做法先搁一搁，假设允许 $O(n^2\log V)$ 通过）。
典型的做法：$f(i,j)$ 表示前 $i$ 个数中选取 $j$ 个数后，和的最大值。$f(i,j)=\max(f(i-1,j),\max_{k}(f(k,j-1)+w(k,i)))$。$w(k,i)=s_i-s_k$，$s$ 是前缀和。
定义 $g(i)$ 表示全局选 $i$ 个区间的最大区间和（$g(j)=\max f(i,j)$）。
$g$ 具有凸性。用贪心的方法证明，你选少的区间自然有些大点吃不到，你选多的区间自然有些负数你不得不吃，选的刚刚好才有最大得分。当然 **写暴力去暴力枚举看下是否凸**，但是不要只找小数据手模，因为可能只是个特例。记住要大胆猜测，论证管他的。
把点 $(i,g(i))$ 放到坐标系上。
$$\tiny\text{让我来偷一个图(https://www.luogu.com.cn/article/knpufhxe)}$$
为了方便说明，记 $p(i,k)$ 表示过 $i$ 的斜率为 $k$ 的直线，截距为 $p(i,k)$。
假设我们知道了经过点 $m$ 的线的 $k$ 和 $p(i,k)$（斜率和截距），显而易见可以求出 $g(m)$。由于 $k$ 任意，不妨找到所有点中某个 $k$ 时 $p(i,k)$ 是最大的（这个为什么能做接下来说）。捋一下，这个时候我们就将问题转换成了这个：
> 找到一个截距 $k$，使得所有点中，$p(m,k)$ 是最大的。
（例如，m=1 时候 k=1.5，m=2 时候 k=0.9）
$$\tiny\text{让我再来偷一张图，网址同上}$$
由于凸性的定义，斜率单调，那么取到 $p$ 极值的时候 $k$ 也是单调的（例如上上个图，分别是 1.5，0.9，0.4，当然不止一个数）。那么我们就可以二分这个 $k$，直到他落到 $m$ 点上！（就像上图一样）
好了，思想铺垫弄完了，咋求这个截距？？？
你将截距公式弄出来：$b_i=y_i-kx_i=g(i)-ki$。你会发现这个就相当于是你选 $i$ 个区间后要被惩罚掉 $ki$。也就是说每次选一个区间，你将受到 $k$ 的惩罚。
你已经有 $k$ 了，定义 $h(i,j)$ 表示在前 $i$ 个数内，选 $j$ 个区间，每选一个区间你将会受到 $k$ 的惩罚，这样子的最大值。
显然：$h(i,j)=\max(h(i-1,j),-k+\max_u (h(u,j-1)+w(u,i)))$。
事实上，你只关心 $\max h(n,j)$ 和取得最值的 $j$。同理可得每个 $i$ 只管 $h$ 最大的 $j$（你贪心地想，你无论选 $2$ 个区间还是 $3$ 个区间，你多选，总是会被惩罚的，与原来不同，永不惩罚。若 $2$ 比 $3$ 还优，选 $3$ 不如选 $2$，因为最终只考虑所有 $j$ 的 $h$ 最值）。
那么 $h$ 的最后一维可以去掉（$h(i)=\max(h(i-1),-k+\max_u(h(u)+w(u,i)))$），多记录一个数，表示取得最大值的 $j$ 是哪个 $j$（因为二分时候要用到）。
这样 $h(n)$ 就是截距最大值了！$j$ 你只需要像二分同款思路一直改变 $k$ 来逼近直到 $j=m$。不具体来说，如果 $j>m$ 咋样咋样，$j\le m$ 咋样咋样。
最终二分内部 chk 需要 $O(n^2)$，总复杂度是 $O(n^2 \log V)$。配合上决策单调性，他会更强。
这里有个我的实现。来自 [P1792 [国家集训队] 种树](https://www.luogu.com.cn/problem/P1792)。
我这里简短的讲一讲，大部分可以自己推。由于是个环，可以做两次 dp，第一次考虑 $1 \sim n-1$，第二次考虑 $2 \sim n$，相当于 $n$ 或 $1$ 每种，自然保证相邻不会挂。dp 可以自己推推，凸性可以自己感性证明。
我的代码有输出方案数的，并且可以处理多点共线，可以参考下。
```cpp
#include <iostream>
#define int long long
typedef long long ll;
using namespace std;
const int N=2e5+5;
int a[N],n,m;
struct Node{
int v,x,ct,fl;
//最大美观度，种了多少棵树，向前多少步，当前位置是否种树&46行左右所使用的标记
Node()=default;
Node(int v,int x,int ct,int fl):v(v),x(x),ct(ct),fl(fl){}
}f[N];
Node add(const Node &a,int x,int y){return Node(a.v+x,a.x+y,a.ct,a.fl);}
Node init(const Node a,int x){return Node(a.v,a.x,a.ct,x);}
Node max(Node a,Node b){
if (a.v>b.v) return a;
if (a.v<b.v) return b;
if (a.x<b.x) swap(a,b);
if (a.x!=b.x && b.ct){return Node(b.v,b.x,b.ct-1,b.fl);}
if (a.ct>b.ct) return b;
return a;
}
bool g[N],ans[N];
Node dp(int l,int r,int k,int mt=0){//mt指的是要向前走多少步（处理共线）
for (int i=l;i<=r;++i){
if (i>=l+2) f[i]=init(f[i-2],0);
else f[i]={0,0,mt,0};
f[i]=max(f[i],init(add(f[i],a[i]+k,1),1));//先转过来再做决策（a[i]+k是个奖励）
if (i>=l+1) f[i]=max(f[i],init(f[i-1],0));
g[i]=f[i].fl;
// cout<<f[i].fl<<"\n";
}
return f[r];
}
Node dp(int k){
return max(dp(1,n-1,k),dp(2,n,k));
}
void solve(){
cin >> n >> m;
for (int i=1;i<=n;++i) cin >> a[i];
if (m==0){
cout<<0<<"\n\n";
return;
}
if (n==1 && m==1){
cout<<a[1]<<"\n";
cout<<1<<"\n";
return;
}
if (m>n/2){
cout<<"Error!\n";
return;
}
int l=-1e9,r=1e9,k,mid;//这里 l 和 r 我一般开 -1e9 到 1e9 无顾虑，由于这里全都是整数，所以可以是整数二分，如果你闲麻烦可以写实数的
while (l<r){
mid=l+r>>1;
// cout<<"wefewfwefewfwefef\n";
if (dp(mid).x>=m) r=mid;
else l=mid+1;
}
cout<<dp(l).v-m*l<<"\n";//减去奖励（这里无论是奖励还是惩罚，本质一样）
int cnt=dp(l).x-m,
p=max(init(dp(1,n-1,l,cnt),1),init(dp(2,n,l,cnt),2)).fl;
dp(p,n+p-2,l,cnt);
for (int i=n+p-2;i>=p;--i) if (g[i]==1) ans[i]=1,--i;
for (int i=p;i<=n+p-2;++i) if (ans[i]) cout<<i<<" ";cout<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;
// cin >> T;
for (int _=0;_<T;++_) solve();
cout.flush();
return 0;
}
//天耀中华，天耀中华
//风雨压不跨，苦难中开花
//祥云飘四方，荣誉传八方
```
典型例题：https://www.luogu.com.cn/problem/P2619 （不用决策单调性的模板题）。
---
决策单调性。
注意：**此处的“决策”是名词“你从哪里转移过来的 dp”，而不是动词。**
那么就可以理解为“你在哪里取得最值”的这个点是单调的。
所有决策单调性都依赖于四边形不等式。先讲四边形不等式。
> 定义 1：若 $w(i,j)$ 满足四边形不等式，对于任意 $a \le b \le c \le d$，满足 $w(a,c)+w(b,d) \le w(a,d)+w(b,c)$。
> 定义 2：任意 $a \le l \le r \le b$，满足 $w(l,r) \le w(a,b)$，则称 $w$ 满足区间包含单调性。
证明某个 $w$ 满足四边形不等式：
1. 自己画数轴暴力拆（这个通常只解决 $w$ 好表示的）（这个挺常用的，其他的都没见过）。
2. 若 $w_1(i,j)$ 和 $w_2(i,j)$ 都满足四边形不等式/恒等式/区间包含单调性，那么任意 $c_1,c_2 \ge 0$，$c_1w_1+c_2w_2$ 满足四边形不等式/恒等式/区间包含单调性。
3. 若存在函数 $f(i)$ 和 $g(i)$（例如前缀和）使得 $w(i,j)=f(i)-g(i)$，那么 $w$ 满足四边形恒等式。若 $f$ 和 $g$ 单调增加、$w$ 还满足区间包含单调性。
4. 若 $h(x)$ 是个单调递增的凸函数，若 $w(i,j)$ 满足四边形不等式并且对区间包含关系有单调性（可增可减），则 $w_1(i,j)=h(w(i,j))$ 满足四边形不等式和区间包含单调性。
5. 若 $h(x)$ 凸，$w(i,j)$ 满足四边形**恒**等式和区间包含关系的单调性，那么 $w_1(i,j)=h(w(i,j))$ 满足四边形不等式。
6. 最最最无敌的方法：如果你看某个 $w$ 非常有四边形不等式，但是死活证明不出来，**写暴力去暴力枚举几组看下决策点是否单调**，但是不要只找小数据手模，因为可能只是个特例。记住要大胆猜测，论证管他的。
接下来我们引入最朴素形式。
> $f(i)=\min/\max_j f(j)+w(j+1,i)$。
记 $\text{opt}(i)$ 表示 $f(i)$ 取得极值时的 $j$（决策点）。
**这个时候若 $w$ 满足四边形不等式，$\text{opt}$ 单调不下降**（超级重要，核心结论）。证明看 OI-WIKI，只需要记住结论就可以了。
写法？这里介绍一种通用的简化 LARSCH 算法（来自 OI-WIKI，非常通用）。
考虑分治，$\text{divide}(l,r)$ 表示求出 $(l..r]$ 的所有 $f$ 值。
定义 $\text{mid}=\lceil\dfrac{l+r}{2}\rceil$，假设这个时候 $l$ 和 $r$ 的 $f$ 和 $\text{opt}$ 都已经部分确定了，那么显然 $\text{opt}_l \le \text{opt}_{\text{mid}} \le \text{opt}_r$。
那么你就可以枚举决策点（$\text{opt}_l$ 和 $\text{opt}_r$ 之间），更新 $\text{mid}$，然后继续递归分裂子问题。这样既可以动态（就是后面的值依赖于前面的 dp 值，普通的分治没法做）做，也可以避开二分队列那样难写的做法。
代码来自 OI-WIKI。
```cpp
val_t w(int j, int i); // 成本函数
val_t f[N]; // 最优值
int opt[N]; // 最小最优决策
// 用决策 j 更新问题 i
void check(int j, int i) {
if (w(j, i) < f[i]) { // 这篇文章的作者加：此处的 w 可以在内部直接加上 f[j]，这样写还简单一些
f[i] = w(j, i);
opt[i] = j;
}
}
// 递归求解区间 (l, r] 内的问题
void calc(int l, int r) {
int mid = (l + r + 1) / 2;
for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);
if (mid < r) calc(l, mid);
for (int j = l + 1; j <= mid; ++j) check(j, r);
if (mid > l) calc(mid, r);
}
// 求解整个区间 [1, n] 内的问题
void solve(int n) {
// 清空 f 数组
std::fill(f + 1, f + n + 1, inf);
// 初始化
check(1, 1);
check(1, n);
// 递归求解区间 (1, n] 内的问题
calc(1, n);
}
```
复杂度显然是 $O(n \log n)$ 的，因为每一大层的复杂度总和总是 $O(n)$，$O(\log n)$ 层，所以是 $O(n \log n)$ 的。可以做做 P3195，即可以斜率也可以决策单调性。
注意这一行：
> `` for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);``
`check` 的右端点 `mid`居然不动，左端点居然一直在非常好的 $+1$。这启示我们一些需要 $O(n)$ 计算的 $w$ 可以类似莫队一样移动指针。例如 $w(l,r)$ 表示 $[l..r]$ 中每个值的出现次数平方（注意这里是分别平方）的和。
这里比较特殊，可以直接先暴力算出 $[\text{opt}_l..\text{mid}]$，然后一个一个往右边走，将左边算过的点删除（比如对于这个例子，可以维护值域数组 `v[i]` 表示值是 $i$ 数的个数，删除的时候先把原来的贡献减去 `ans-=v[i]*v[i]`，`--v[a[i]]`，再加上现在的贡献 `ans+=v[i]*v[i]`）。还有一种方法就是暴力算出 $[\min(\text{opt}_r,\text{mid})..\text{mid}]$，然后再加入。可以看 CF868F。同时那道题也要分层，可以练手。
接下来我们解决形式 2（区间 dp 形式，用的较少）。
> 形式 2：在一个操场上摆放着一排 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
> 试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小得分。$N \le 2000$。P5569 弱化版。
显然最朴素的方程是 $f(l,r)=\min_k f(l,k)+f(k+1,r)+w(l,r)$。
这个时候 $w$ 显然满足四边形不等式和区间包含单调性。所以这个时候有结论（1）：$f$ 满足四边形不等式。
这个时候 $f$ 满足四边形不等式，则有结论（2）：$\text{opt}_{l,r-1} \le \text{opt}_{l,r} \le \text{opt}_{l+1,r}$。
那么我们就可以直接枚举决策点区间去做。由于对于每个 $l$，遍历的长度总和是 $O(n)$ 的，所以复杂度是 $O(n^2)$ 的。（这个很少用）
好了，决策单调性讲完了，这个时候我们就可以回收 wqs 所留的问题了。把式子拿过来：$h(i)=\max(h(i-1),-k+\max_u(h(u)+w(u,i)))$。$w$ 可是满足四边形恒等式啊！具有决策单调性了啊！做完了（这里不影响 wqs 所需要记录的最优次数），时间复杂度 $O(n \log n)$，算上 wqs 二分就是 $O(n \log n \log V)$，略逊于反悔贪心。
他和凸性的关系？咱们回到原来 wqs 二分的式子来。$f(i,j)=\max(f(i-1,j),\max_{k}(f(k,j-1)+w(k,i)))$。
这里直接给出结论：$g(j)=\max f(i,j)$ 具有凸性。这个非常有用，返回原来的 wqs 问题，就可以直接证明它有凸性了。还有更多的证明凸性可以见 [oi-wiki](https://oi-wiki.org/dp/opt/wqs-binary-search/#%E5%87%B8%E6%80%A7%E8%AF%81%E6%98%8E)。
非常感谢：https://oi-wiki.org/dp/opt/quadrangle/
---
好的，让我们来看一道非常综合的题目！
[题目](https://www.luogu.com.cn/problem/P9338)。
**题目大意**
> 给定一个 $n$ 个 $\texttt{A}$ 和 $n$ 个 $\texttt B$ 组成的字符串 $S$，交换最少对元素使得：
>
> 存在一种方式，把 $S$ 划分为 $k$ 个子序列，每个子序列 $\texttt{A},\texttt B$ 数量相等且所有 $\texttt A$ 在所有 $\texttt B$ 左边。
>
> 数据范围：$n\le 10^6$。（来自 DaiRuiChen007 的题解，https://www.luogu.com.cn/article/amcj6rjb ）
这里的题解都是基于 https://www.luogu.com.cn/article/amcj6rjb 理解的，讲的非常简短，但是有点笔误，代码中 `inline array<ll,2> check(ll x)` 使用 array 作为返回值，确实强！我这里主要是想讲的清楚一点。
遇见难题，先想想超级暴力咋做，一般是有前途的。
由于是子序列划分，所以普通的“$f(i,j)$ 表示前 $i$ 个数划分为 $j$ 段，这个状态的最小交换次数”完全不可做（他那个选的东西又不连续），所以考虑其他的。
换一个方面想，假设原序列就有解，先将 A 和 B 匹配，然后再把某些东西组合起来，这样也可以得到答案。
这启发我们将匹配的个数放到状态里。**定义 $f(i,j)$，表示将前 $i$ 个 A 和 B 安排到了前 $j$ 个乐曲，这样的最小交换次数。**（后面我相信读者可以自己推出来）
这个时候也就有了一个非常好的性质：同一个乐曲中，选出来的 A 的次第是个区间。这个也很好证，如果不是个区间，反而不优（可以通过举例法或感性理解来猜到这个结论）。这里给个感性证明：你想咋选咋选，反正“区间”这一选法是一定存在在最优集合里面的。
这个就刚好解决了选点不连续的问题，那么 $f(i,j)=\min\limits^{i-1}_{k=0}f(k,j-1)+w(k+1,i)$。$w(l,r)$ 表示将第 $[l..r]$ 个 A 和第 $[l..r]$ 个 B 安排成一个合法的队伍需要的最少次数。
设 $p_i$ 表示第 $i$ 个 A 前面有多少个 B，那么 $w(l,r)=\sum\limits^{r}_{i=l}\max(0,p_i-l+1)$。解释：这里是要将多少个 B 换到后面才有戏。
这个四边形不等式能证明（见后面），但是可以通过打表来证明。这个凸性也就证明出来了。由于 $w$ 满足四边形不等式，所以 $g(i)$ 具有凸性。
这里我们选择 wqs 二分。这样是 $O(n \log n \log V)$ 的，但是此题 $n \le 10^6$。但是恭喜你获得了 $87$ 分！所以考虑更优的做法。
考虑将 $w$ 优化。这个 $w$ 拆开就是个 $s$（前缀和）和 $q$（这里 $q_x$ 指的是第一个 $i$ 使得 $p_i \ge x$ 的 $i$）的表示了，你拆开就可以了。
这里由于 $p$ 有决策单调性（？）所以你算 $q_i$ 的时候可以直接找到 $q_{i-1}$ 然后再往后遍历。这样是 $O(n)$ 的。这样处理比较舒服。
把上面的 $w$ 的式子拿过来，$w(l,r)=\sum\limits^{r}_{i=l}\max(0,p_i-l+1)$。那么 $w(l,r)=\sum\limits^{r}_{i=p_{l-1}}(p_i-l+1)=s_r-s_{p_{l-1}-1}-(r-p_{l-1}+1)\times(l-1)$（这里 $s_i=\sum\limits^{i}_{j=1}p_i$）。
这里来证明四边形不等式：首先 $s$ 抵消，然后你把位拆开，发现两项（两个乘法）中都是左边小于等于右边的（遇到这种题，大胆猜结论，如果你想在考场上证明，因为拆式子过于费劲，那耗费的时间足够重新写一份了）。
那么 $g(i)=\min_j g(j)+w(j+1,i)=\min_j g(j-1)+w(j,i)=\min_j (g(j-1)+s_i-s_{p_{j}-1}-(i-p_{j}+1)\times j)=\min_j ((g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)+s_i+i\times j)$（这里告诉一个非常好的公式换元方法：直接在小熊猫使用ctrl+f替换模式）（g 是 wqs 用）。
具体地（让我们来复习凸包！），当式子满足了这个标准形式：$f(i)=\max _j y_j-k_ix_j$ 就可以进行斜率优化（这里的 max 是 min 也可以）。这个时候 $f(i)$ 就相当于这条斜线的 b 值。
回到原来，$g(i)=s_i+\min_j ((g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)+i\times j)$。这个时候令 $y_j=(g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)$，$x_j=j$，$k_i=-i$，就可以做了。此时，显然，$k$ 满足单调递减，$x$ 满足单调递增，所以可以考虑一下直接拿单调栈来实现 $O(n)$ 做 dp。
由于 $x$ 越来越大，可以维护单调栈直接来维护凸包。又由于 $k$ 单调递减，而凸包的性质满足它的 b 值是一个单谷函数，且谷底决策点一定从左向右移动。所以可以维护指针。这样我们就用 $O(n \log V)$ 做完了（这里的 $V$ 其实和 $n$ 是同阶的）！