slope trick 学习笔记
jrxxx
·
·
算法·理论
功能
slope trick 是一种依赖凸性优化一类最优化 DP 的 trick。
可以优化连续分段凸函数的相加、平移、min/max等操作。
一般要求每段为一次函数，且斜率为整数。
核心思想
对于一个凸函数（以下凸为例），尝试以如下方式来表示：
记录下最左边第一段的表达式 y=kx+b，再用可重集 S 记录每次斜率增加 1 的位置横坐标。
例如：
\begin{aligned}
|w-x|&\rightarrow(y=-x+w,\{w,w\})\\
\max(0,w-x)&\rightarrow (y=-x+w,\{w\})\\
\max(0,x-w)&\rightarrow (y=0,\{w\})
\end{aligned}
这样表示的好处可以在一些操作中体现出来：
以下所有讨论默认分段函数中存在斜率为 0 的一段。
相加
## 找最值点
下凸函数一般求最小值。
即找斜率为 $0$ 的线段（可能两端点重合），这条线段以下称为 $0$ 线段。
常用一个大根堆 $L$ 和一个小根堆 $R$ 来维护拐点，$L$ 中存储目标线段左侧的拐点，$R$ 中存储目标线段右侧的拐点。$L.top$ 和 $R.top$ 即为 $0$ 线段的两端点。
维护方法是：始终保证 $k+L.size()=0$，将多余拐点扔进 $R$。
当 $k$ 减小时，要记得先从 $R$ 中取点补进 $L$，再加入新的拐点。
## 前后缀 min
以前缀 min 为例。
其实就是扔掉了 $R$ 堆中的所有拐点。
实现时可以只维护 $L$ 堆。
## 平移
$y=kx+b$ 的平移不多赘述了，初中数学知识。
$S$ 的平移就是在堆上打 tag。
## 截取
上述讨论都是在 $x\in[-\inf,\inf]$ 上进行的，没有考虑定义域。
当要求 $x\in[l,r]$ 的函数最小值时，最小值可能不在 $0$ 线段上而在端点上。
将所有拐点都和 $l$ 取 $\min$，和 $r$ 取 $\max$ 即可，不会改变在 $[l,r]$ 内的函数取值，且能将最小值放进 $[l,r]$。
实现时在将拐点加入堆时直接取 $\min/\max$。但是如果同时还有平移操作，理论上可能会寄（平移至定义域外），但是我还没见过会寄的题，因为这些题在平移点的同时也平移或扩大了定义域。
还有个别题性质较好，可以在将点取出堆时再调整，这大概要求平移都是同方向的（？），我没太想清楚，建议使用上一种方法。这种方法在下面两道需要截取的例题中一个能做，一个寄了，但是上面那种两个都可以。
# 输出答案
slope trick 输出答案有两种方法。
第一种是直接还原出最终分段函数，扫一遍。
第二种是倒推出所有决策点，即方案，再依据此求答案。决策点的转移通常与 $0$ 线段端点有关，需要在过程中记录下来。
前一种比较暴力无脑。
后一种可以应对输出方案的题，而且因为不用还原函数，一次函数 $y=kx+b$ 中就只用维护 $k$，不用维护 $b$。
下面例题的代码多采用第二种。
# 题目
以下参考代码常数较大，可以优化，但是这样方便理解。
- [[BalticOI2004] Sequence数字序列](https://www.luogu.com.cn/problem/P4331)
先将 $a_i,b_i$ 每位减 $i$，答案不变，$b_i$ 的限制由单调递增变为单调不降。
设 $f_{i,j}$ 表示填完前 $i$ 位，第 $i$ 位 $\le j$ 的最小答案。
转移：$f_{i,j}=\min(f_{i-1,j}+|a_i-j|,f_{i,j-1})$。
分两步来理解就是：先加上 $|a_i-j|$，再取前缀 $\min$。都是 slope trick 经典操作。
本题需要输出方案。记录下每个 $f_i(j)$ 的 $0$ 线段左端点。
两步操作决策点前一步继承，后一步前缀取 $\min$。于是倒推时将 $0$ 线段左端点取后缀 $\min$ 即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,a[N],pos[N],stk[N],top;
priority_queue<int> q;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,k;
long long ans;
cin>>n;
for(i=1;i<=n;++i) cin>>a[i],a[i]-=i;
for(i=1;i<=n;++i)
{
//add |a_i-j| -> (y=-x+a_i,{a_i,a_i})
k+=-1;
q.push(a[i]),q.push(a[i]);
//prev min
while(k+q.size()>0) q.pop();
pos[i]=q.top();
}
//calc real decision points (pos)
for(i=n-1;i>=1;--i) pos[i]=min(pos[i],pos[i+1]);
//calc ans
ans=0;
for(i=1;i<=n;++i) ans+=abs(a[i]-pos[i]);
for(i=1;i<=n;++i) cout<<pos[i]+i<<" \n"[i==n];
return 0;
}
```
---
- [[CTSC2009] 序列变换](https://www.luogu.com.cn/problem/P4272)
设 $f_{i,j}$ 表示填完前 $i$ 位，第 $i$ 位等于 $j$ 时的最小答案。
转移：$f_{i,j}=\min_{k\in[l,r]\land j-k\in[1,m]}\{f_{i-1,j-k}\}+|a_i-j|$。
第一步：$f'(j)=\min_{k\in[l,r]\land j-k\in[1,m]}\{f(j-k)\}$。
先不考虑 $[1,m]$ 限制，可以发现转移可以对于斜率 $0\rightarrow -1$ 的拐点横坐标 $p$ 分两类讨论。
$$
f'(j)=
\begin{cases}
f(j-l)&(j\le p+l)\\
f(p)&(p+l<j\le p+r)\\
f(j-r)&(j>p+r)
\end{cases}
$$
图形化来说，就是将 $p$ 之前的拐点都向右平移 $l$，$p$ 以及 $p$ 之后的拐点都向右平移 $r$。按 $p$ 分到两个堆里分别打 tag 即可。
至于区间限制，将所有拐点横坐标与 $1+(i-1)\cdot l$ 取 $\min$，和 $m-(n-i)\cdot l$ 取 $\max$。将横坐标插入堆或从堆内取出时做 $\min/\max$，本题这两种方法均可。
第二步：$f'(j)=f(j)+|a_i-j|$。经典操作。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+7;
int n,m,l,r,a[N],b[N];
priority_queue<ll> lq;
priority_queue<ll,vector<ll>,greater<ll>> rq;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,k;
ll ans,ltag,rtag;
cin>>n>>m>>l>>r;
ltag=rtag=0,k=0;
for(i=1;i<=n;++i)
{
cin>>a[i];
//min[j-l,j-r] -> j
ltag+=l,rtag+=r;
//add |a_i-j| (y=-x+a_i,{a_i,a_i})
k+=-1;
while(!rq.empty()&&k+(int)lq.size()<0)
lq.push(rq.top()+rtag-ltag),rq.pop();
lq.push(a[i]-ltag);
lq.push(a[i]-ltag);
while(k+(int)lq.size()>0)
rq.push(lq.top()+ltag-rtag),lq.pop();
b[i]=rq.top()+rtag;
b[i]=min(max(b[i],1+(i-1)*l),m);
}
//calc real decision points
b[n]=max(b[n],1+(n-1)*l);
for(i=n-1;i>=1;--i)
{
if(b[i+1]-r>b[i]) b[i]=b[i+1]-r;
else if(b[i+1]-l<b[i]) b[i]=b[i+1]-l;
}
//calc ans
ans=0;
for(i=1;i<=n;++i) ans+=abs(a[i]-b[i]);
cout<<ans<<'\n';
return 0;
}
```
---
- [[ABC217H] Snuketoon](https://www.luogu.com.cn/problem/AT_abc217_h)
设 $f_{i,j}$ 表示 $T_i$ 时刻到达 $j$ 位置的最小答案。
如果 $D_i=0$：$f_{i,j}=\min\limits_{|j-k|\le T_i-T_{i-1}}\{f_{i-1,k}\}+\max(0,X_i-j)$。
如果 $D_i=1$：$f_{i,j}=\min\limits_{|j-k|\le T_i-T_{i-1}}\{f_{i-1,k}\}+\max(0,j-X_i)$。
平凡的平移再相加操作，和上一道基本一样，根据 $0$ 线段端点分类讨论一下即可。
本题中也有 $j$ 的范围限制：$\forall f_i(j),j\in[-T_i,T_i]$，只能将横坐标加入堆时做 $\min/\max$。
同样记下 $R.top$，方便倒推决策点。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+7,inf=0x7f7f7f7f;
int n,op[N],t[N],a[N],res[N],pos[N];
priority_queue<ll> lq;
priority_queue<ll,vector<ll>,greater<ll>> rq;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,ltag,rtag,k,p,d;ll ans;
cin>>n;
ltag=rtag=0,k=0;
for(i=1;i<=n;++i)
{
cin>>t[i]>>op[i]>>a[i];
d=t[i]-t[i-1];
//min[j-d,j+d] -> j
ltag-=d,rtag+=d;
//add 0:(y=0,{p}) 1:(y=-x+p,{p})
k+=op[i]?0:-1;
while(!rq.empty()&&k+(int)lq.size()<0)
lq.push(rq.top()+rtag-ltag),rq.pop();
p=min(t[i],max(-t[i],a[i]));
lq.push(p-ltag);
while(k+(int)lq.size()>0)
rq.push(lq.top()+ltag-rtag),lq.pop();
//get pos
pos[i]=rq.empty()?t[i]:rq.top()+rtag;
}
//calc real decision points
res[n]=pos[n];
for(i=n-1;i>=1;--i)
{
d=t[i+1]-t[i];
if(res[i+1]>=pos[i]) res[i]=max(pos[i],res[i+1]-d);
else res[i]=min(pos[i],res[i+1]+d);
}
//calc ans
ans=0;
for(i=1;i<=n;++i)
ans+=op[i]?max(0,res[i]-a[i]):max(0,a[i]-res[i]);
cout<<ans<<'\n';
return 0;
}
```
---
- [[ARC070C] NarrowRectangles](https://www.luogu.com.cn/problem/AT_arc070_c)
和上一题转移几乎一模一样。
定义域为 $\mathbb{Z}$，不用截取。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+7;
const ll inf=0x7f7f7f7f7f7f7f7f;
int n,l[N],r[N],len[N];
ll pos[N],res[N];
priority_queue<ll> lq;
priority_queue<ll,vector<ll>,greater<ll>> rq;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,k;ll ltag,rtag,ans;
cin>>n;
for(i=1;i<=n;++i)
cin>>l[i]>>r[i],len[i]=r[i]-l[i];
ltag=rtag=0,k=0;
for(i=1;i<=n;++i)
{
//min [j-len_{i-1},j+len_i] -> j
ltag-=len[i],rtag+=len[i-1];
//add |j-l[i]|
k+=-1;
while(!rq.empty()&&k+(int)lq.size()<0)
lq.push(rq.top()+rtag-ltag),rq.pop();
lq.push(l[i]-ltag);
lq.push(l[i]-ltag);
while(k+(int)lq.size()>0)
rq.push(lq.top()+ltag-rtag),lq.pop();
pos[i]=rq.empty()?inf:rq.top()+rtag;
}
res[n]=pos[n];
ans=abs(l[n]-res[n]);
for(i=n-1;i>=1;--i)
{
if(res[i+1]>=pos[i]) res[i]=max(pos[i],res[i+1]-len[i]);
else res[i]=min(pos[i],res[i+1]+len[i+1]);
ans+=abs(l[i]-res[i]);
}
cout<<ans<<'\n';
return 0;
}
```
---
- [[APIO2016] 烟火表演](https://www.luogu.com.cn/problem/P3642)
---
- [[CF1534G] A New Beginning](https://www.luogu.com.cn/problem/CF1534G)