Slope Trick 总结
注意：Slope Trick 并不是斜率优化，斜率优化的英文是 Convex Hull Trick。
算法适用性
Slope Trick 通常用于维护具有如下性质的函数：
- 连续。
- 是分段一次函数。
- 是凸函数。
- 每一段的斜率较小（通常为 \(O(n)\)），且均为整数。
常常用于优化动态规划。
不失一般性，约定本文中的函数均为下凸，且称以上所有性质为性质 \(P\)。
注意到，两个满足性质 \(P\) 的函数相加，得到的函数依然满足性质 \(P\)。
算法思想
维护在某个 \(x_0\) 处的 \(f(x_0),k_0\) 以及函数每个斜率变化点的集合。具体地，如果函数在 \(x\) 位置斜率增加了 \(\Delta k\)，就在集合中插入 \(\Delta k\) 个 \(x\)。
性质 \(P\) 十分优美，它使得我们可以快速维护很多操作：
- 相加：将 \(f(x_0),k_0\) 直接相加，斜率变化点的集合直接合并。常用于加一次函数、绝对值函数。
- 取前缀/后缀 \(\min\)：去掉 \(k<0\) 或 \(k>0\) 的部分。
- 求 \(\min,\operatorname{argmin}\)：提取 \(k=0\) 部分。
- 平移：维护 \(f(x_0),k_0\) 变化，斜率变化点在全局打平移标记。
- 翻转：维护 \(f(x_0),k_0\) 变化，斜率变化点在全局打翻转标记。
例题：P4597 序列 sequence
设 \(f_{i,j}\) 表示考虑 \([1,i]\) 的前缀，把最后一个数变为 \(j\) 的最小操作次数。显然有转移方程：
\[f_{i,j}=\min_{k\le j}\{f_{i-1,k}\}+|a_i-j| \]设 \(F_i(j)=f_{i,j}\)。显然，\(F_i\) 可以由 \(F_{i-1}\) 先取前缀 \(\min\) 再加绝对值函数得到。所求即为 \(\min F_n\)。
由于 \(F_i\) 满足性质 \(P\)，使用堆维护斜率变化点即可。
代码
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 5e5+5;
ll n, a[N], ans;
priority_queue<ll> q;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
scanf("%lld", &n);
rep(i, 1, n) {
scanf("%lld", &a[i]);
if(!q.empty() && q.top() > a[i]) {
ans += q.top() - a[i];
q.pop();
q.push(a[i]);
}
q.push(a[i]);
}
printf("%lld\n", ans);
return 0;
}
四倍经验：CF713C Sonya and Problem Wihtout a Legend、CF13C Sequence、P2893 [USACO08FEB] Making the Grade G
与该题几乎完全一致。
习题：LCP24 数字游戏
Slope Trick 简单题，也有对顶堆等做法。
习题：P3642 [APIO2016] 烟火表演
可并堆维护 Slope Trick。
代码
// Problem: P3642 [APIO2016] 烟火表演
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3642
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
const ll N = 6e5 + 5;
ll n, m, f[N], d[N], deg[N], ans;
struct LeftistTreeNode {
ll lc, rc, val, dis;
LeftistTreeNode(ll val = 0, ll dis = 0) : lc(0), rc(0), val(val), dis(dis) {}
};
struct LeftistTree {
LeftistTreeNode t[N];
ll rt[N], sz;
ll newnode(ll val) {
t[++sz] = LeftistTreeNode(val);
return sz;
}
ll merge(ll u, ll v) {
if(!u || !v) return u | v;
if(t[u].val < t[v].val) swap(u, v);
t[u].rc = merge(t[u].rc, v);
if(t[t[u].lc].dis < t[t[u].rc].dis) swap(t[u].lc, t[u].rc);
t[u].dis = t[t[u].rc].dis + 1;
return u;
}
ll merge(ll u, ll v, ll args...) {
return merge(merge(u, v), args);
}
ll seek(ll u) {
return t[u].val;
}
void pop(ll& u) {
u = merge(t[u].lc, t[u].rc);
}
}leftree;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
rep(i, 2, n + m) cin >> f[i] >> d[i];
rep(i, 2, n + m) ++deg[f[i]], ans += d[i];
per(u, n + m, 2) {
while(deg[u]-- > 1) leftree.pop(leftree.rt[u]);
ll r = leftree.seek(leftree.rt[u]);
leftree.pop(leftree.rt[u]);
ll l = leftree.seek(leftree.rt[u]);
leftree.pop(leftree.rt[u]);
leftree.rt[u] = leftree.merge(leftree.rt[u], leftree.newnode(l + d[u]), leftree.newnode(r + d[u]));
leftree.rt[f[u]] = leftree.merge(leftree.rt[f[u]], leftree.rt[u]);
}
while(deg[1]--) leftree.pop(leftree.rt[1]);
while(leftree.rt[1]) {
ans -= leftree.seek(leftree.rt[1]);
leftree.pop(leftree.rt[1]);
}
cout << ans << endl;
return 0;
}