专栏文章

青春猪头少年不会梦到 Slope Trick 学姐

llovely_nst
算法·理论参与者 11已保存评论 10

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
10 条
当前快照
1 份
快照标识符
@mlia22g9
此快照首次捕获于
2026/02/12 01:02
上周
此快照最后确认于
2026/02/19 01:11
13 小时前
查看原文
我的 Slope Trick 题单

前言

本文讲的 Slope Trick 与传统 Slope Trick 在求得答案的过程有少量差别，个人感觉更好理解。
本文存在大量平衡树。

Slope Trick 简介

Slope Trick 就是用数据结构维护呈凸性的 DP 值以优化复杂度。常见的形式有：
fi,j=∣j−ai∣+min⁡k=LjRjfi−1,kf_{i,j}=\left|j-a_i\right|+\min_{k=L_j}^{R_j} f_{i-1,k}
由于绝对值函数是凸函数，因此经常在 Slope Trick 相关题目中出现。

凸函数

在 Slope Trick 中一般提到的都是下凸函数。
上图就是常见的凸函数，其具有几个性质：
  • 凸函数上相邻的两点的斜率随着横坐标的增加而递增（这一性质是大部分斜率优化题目的根基，可以用二分，单调栈，优先队列等维护）
  • 两个凸函数按位相加后还是凸函数（把凸包按位加和斜率想象成序列相加和差分数组，两个递增的差分数组相加还是递增的）

Slope Trick

结合例题讲解。

例题 1 P4597 序列 sequence

题意

给定一个序列，每次操作可以把某个数 +1+1 或 −1−1。要求把序列变成非降数列。

暴力

设 fi,jf_{i,j} 表示枚举到第 ii 位，这一位变成了 jj 的最小操作次数。
容易得到：
fi,j=min⁡k=1jfi−1,k+∣j−ai∣f_{i,j}=\min_{k=1}^j f_{i-1,k}+\left|j-a_i\right|
于是我们就有了 O(nV2)O(nV^2) 的暴力 DP 了，加上前缀和可以进一步优化。

正解

发现 ∣j−ai∣\left|j-a_i\right| 与 kk 无关，可以提前。那么原式变为：
fi,j=∣j−ai∣+min⁡k≤jfi−1,kf_{i,j}=\left|j-a_i\right|+\min_{k\le j} f_{i-1,k}
考虑 f(x)=∣x−v∣f(x)=\left|x-v\right| 函数长啥样的。
当 x<vx<v 时，f(x)f(x) 随 xx 递减而递增，斜率为 −1-1。
当 x>vx>v 时，f(x)f(x) 随 xx 递增而递增，斜率为 11。
因此是凸的。
设 fi(x)=fi,xf_i(x)=f_{i,x}，那么 f0(x)=0f_0(x)=0 也可以看作是凸的。
对一个凸函数 f(x)f(x) 做前缀 min⁡\min 可以分类讨论：
  • 当 f(i)<f(i−1)f(i)<f(i-1) 时（斜率为负），f(i)f(i) 更优。
  • 当 f(i)=f(i−1)f(i)=f(i-1) 时（斜率为 00），f(i)f(i) 取全局最小值。
  • 当 f(i)>f(i−1)f(i)>f(i-1) 时（斜率为正），因为到 ii 时已经经过上一种情况，因此 f(i)≥min⁡f(x)f(i)\ge \min f(x)，f(i)f(i) 取全局最小值。
由上，做前缀 min⁡\min 可以看成将后面一段斜率为正的推平成全局最小值（即修改斜率为 00），因此做完还是凸的。
因为凸函数相加还是凸函数，可以推得 fi(x)f_i(x) 是凸的。
考虑用优先队列维护拐点横坐标，每经过一个拐点斜率加 11（当在一个位置的斜率差大于 11 时也要对应加入相同个数的拐点），加绝对值函数相当于在 aia_i 处加入两个拐点（−1-1 和 11 差了 22，加入后斜率差也会加 22）。
做完前面的，目前第一条直线的斜率会是 −i-i（因为加入了 ii 个绝对值函数，当一个点的横坐标比 aia_i 的最小值还小时，所有绝对值函数的贡献均为 −1-1，斜率就会是 −i-i）。做前缀 min⁡\min 推平就是只保留前 ii 个拐点（只保留斜率为 −i-i 到 00 的直线，对应的只有 ii 个拐点）。
以下与传统 Slope Trick 有差别
最后计算答案，我们先计算 fn,−inff_{n,-inf}，最后暴力计算斜率为 00 的平台的高度，即暴力还原凸函数。
具体见代码。
AC CodeCPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 2e9;
priority_queue <int> q;
stack <int> s;
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	int n;
	cin >> n;
	int f = 0;
	for (int i = 1;i <= n;i ++)
	{
		int x;
		cin >> x;
		f += x + inf; // f[n][-inf]
		q.push (x);
		q.push (x);
		// 加入两个拐点
		q.pop (); // min 推平
	}
	while (!q.empty ()) s.push (q.top ()) , q.pop ();
	int lst = -inf;
	for (int i = n;i >= 1;i --)
		f -= (s.top () - lst) * i , lst = s.top () , s.pop ();
    // 暴力还原凸函数
	cout << f;
	return 0;
}
相较于传统维护平台的方法，这样更加直接，但也存在缺陷（见例二）。

例二 P11598 [NOISG 2018 Finals] Safety

题意

给定一个序列，每次操作可以把某个数 +1+1 或 −1−1（不能小于 00）。给定 hh，要求序列满足：
∀i>1,∣ai−ai−1∣≤h\forall i>1,\left|a_i-a_{i-1}\right|\le h

题解

设 fi,jf_{i,j} 表示枚举到第 ii 位，改位最终为 jj 的最小操作次数。容易得到方程：
fi,j=min⁡k=max⁡(j−h,0)j+hfi−1,k+∣j−ai∣f_{i,j}=\min_{k=\max(j-h,0)}^{j+h} f_{i-1,k}+\left|j-a_i\right|
通过斜率为 00 的区间 [L,R]\left[L,R\right] 分类讨论：
  • j+h≤Lj+h\le L 时，最小值为 fi−1,j+hf_{i-1,j+h}。
  • j−h≥Rj-h\ge R 时，最小值为 fi−1,j−hf_{i-1,j-h}。
  • 其余情况，[j−h,j+h]\left[j-h,j+h\right] 一定可以取到 [L,R]\left[L,R\right] 内的任意位置，最小值为全局最小值。
因此可以使用平衡树切割区间维护拐点。对于左侧（LL 那一侧），fi,j=fi,j+hf_{i,j}=f_{i,j+h}，也就是拐点横坐标集体减 hh；对于右侧（RR 那一侧），fi,j=fi,j−hf_{i,j}=f_{i,j-h}，也就是拐点横坐标集体加 hh。
之后的流程都是一样的，不同点在 fn,0f_{n,0} 的计算。
由转移方程可以得到：
fi,0=min⁡k=0hfi−1,k+aif_{i,0}=\min_{k=0}^{h} f_{i-1,k}+a_i
普通堆无法做到双向获取值，因此使用平衡树或 set 维护。

AC Code

FHQ TreapCPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
mt19937 rd (time (0));
struct Treap
{
	int cc = 0;
	struct Node
	{
		int l , r , v , w , sz , tag;
	} tr[N];
	int get_new (int x) // 创建节点
	{
		tr[++ cc] = {0 , 0 , x , rd () , 1};
		return cc;
	}
	void push_down (int p) // 下传标记
	{
		if (tr[p].tag)
		{
			tr[tr[p].l].v += tr[p].tag;
			tr[tr[p].r].v += tr[p].tag;
			tr[tr[p].l].tag += tr[p].tag;
			tr[tr[p].r].tag += tr[p].tag;
			tr[p].tag = 0;
		}
	}
	void add (int p , int x) {tr[p].v += x , tr[p].tag += x;} // 子树加
	void spl (int p , int x , int &l , int &r) // <= x 分裂
	{
		if (!p)
		{
			l = r = 0;
			return ;
		}
		push_down (p);
		if (tr[p].v <= x)
		{
			l = p;
			spl (tr[p].r , x , tr[p].r , r);
		}
		else
		{
			r = p;
			spl (tr[p].l , x , l , tr[p].l);
		}
		tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
	}
	void splsz (int p , int x , int &l , int &r) // 长度 < x 分裂
	{
		if (!p)
		{
			l = r = 0;
			return ;
		}
		push_down (p);
		if (tr[tr[p].l].sz < x)
		{
			l = p;
			splsz (tr[p].r , x - tr[tr[p].l].sz - 1 , tr[p].r , r);
		}
		else
		{
			r = p;
			splsz (tr[p].l , x , l , tr[p].l);
		}
		tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
	}
	int mrg (int l , int r) // 合并
	{
		if (!l || !r)
			return l | r;
		if (tr[l].w <= tr[r].w)
		{
			push_down (l);
			tr[l].r = mrg (tr[l].r , r);
			tr[l].sz = tr[tr[l].l].sz + tr[tr[l].r].sz + 1;
			return l;
		}
		else
		{
			push_down (r);
			tr[r].l = mrg (l , tr[r].l);
			tr[r].sz = tr[tr[r].l].sz + tr[tr[r].r].sz + 1;
			return r;
		}
	}
	void ins (int &rt , int x) // 加入新点
	{
		int rl , rr;
		spl (rt , x - 1 , rl , rr);
		rt = mrg (mrg (rl , get_new (x)) , rr);
	}
	int get (int p , int x) // 获取第 x 位的值
	{
		while (true)
		{
			push_down (p);
			int u = tr[tr[p].l].sz + 1;
			if (u == x)
				return tr[p].v;
			if (x >= u) p = tr[p].r , x -= u;
			else p = tr[p].l;
		}
		return -1;
	}
	int size (int rt) {return tr[rt].sz;} // 子树大小
} T;
int n , h , a[N];
int rt;
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	cin >> n >> h;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	int sl = -1 , f0 = a[1]; // sl 维护第一段的斜率，f0 维护 f[i][0]
	T.ins (rt , a[1]) , T.ins (rt , a[1]); // 加入绝对值函数
	for (int i = 2;i <= n;i ++)
	{
		int L , R , calc;
		T.splsz (rt , -sl , L , R); // 将其从斜率为 0 的段拆开
		T.spl (L , h , calc , L); // 原本横坐标 <= h 的拐点会被删除
		int lst = 0;
		for (int i = 1;i <= T.size (calc);i ++)
		{
			f0 += sl * (T.get (calc , i) - lst) , lst = T.get (calc , i);
			sl ++; // 删除一段（一个拐点），下一段斜率加一
		}
		f0 += sl * (h - lst);
		f0 += a[i];
		// 原本横坐标 <= h 的拐点计算新的 f[i][0]
		T.add (L , -h); // 左侧 -d
		T.add (R , h); // 右侧 +d
		rt = T.mrg (L , R);
		T.ins (rt , a[i]) , T.ins (rt , a[i]); // 加入绝对值函数
		sl --; // 加入后 a[i] 之前的斜率减一，从而第一段斜率也要减一
	}
	int lst = 0;
	for (int i = 1;i <= T.size (rt);i ++)
	{
		if (sl >= 0) break; // 仅计算最低点，之后会开始上升，不计入答案
		f0 += sl * (T.get (rt , i) - lst);
		lst = T.get (rt , i);
		sl ++;
	}
	cout << f0;
	return 0;
}
SetCPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
mt19937 rd (time (0));
struct Set
{
	int tag = 0;
	multiset <int> s;
	inline void insert (int x) {s.insert (x - tag);}
	inline void add (int x) {tag += x;}
	inline int front () {return (*s.begin ()) + tag;}
	inline int back () {return (*(-- s.end ())) + tag;}
	inline void pop_front () {s.erase (s.begin ());}
	inline void pop_back () {s.erase (-- s.end ());}
	inline int size () {return s.size ();}
	inline bool empty () {return s.empty ();}
} TL , TR;
int n , h , a[N];
int rt;
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	cin >> n >> h;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	int sl = -1 , f0 = a[1]; // sl 维护第一段的斜率，f0 维护 f[i][0]
	TL.insert (a[1]) , TR.insert (a[1]); // 加入绝对值函数
	for (int i = 2;i <= n;i ++)
	{
		int lst = 0;
		while (!TL.empty ())
		{
			int p = TL.front ();
			if (p > h) break;
			TL.pop_front ();
			f0 += sl * (p - lst);
			lst = p;
			sl ++;
		}
		f0 += sl * (h - lst);
		f0 += a[i];
		TL.add (-h);
		TR.add (h);
		int R = TR.front ();
		if (a[i] < R)
		{
			TL.insert (a[i]) , TL.insert (a[i]);
			TR.insert (TL.back ());
			TL.pop_back ();
		}
		else
		{
			TR.insert (a[i]) , TR.insert (a[i]);
			TL.insert (TR.front ());
			TR.pop_front ();
		}
		sl --;
	}
	int lst = 0;
	for (int p : TL.s)
	{
		if (sl >= 0) break;
		f0 += sl * (p + TL.tag - lst);
		lst = p + TL.tag;
		sl ++;
	}
	cout << f0;
	return 0;
}

其它 Slope Trick

P13954 红黑树

题意

给定 nn 个点的树，每个节点有红黑之一的颜色。对于每个节点 kk，求最少翻转节点颜色的次数，使得以 kk 为根的子树中任意节点 uu 都满足：从 uu 出发到其所有后代叶子节点的简单路径上所经过的黑色节点数量相等。

暴力

设 fu,if_{u,i} 表示点 uu 为根的子树中的叶子节点到 uu 的路径上黑点个数均为 ii，此时的最小修改数。
分两种情况考虑。
第一种，点 uu 的颜色最终为红色，可得转移方程：
fu,i=[su=1]+∑v∈son(u)fv,if_{u,i}=\left[s_u=1\right]+\sum_{v\in \text{son}(u)} f_{v,i}
第二种，点 uu 的颜色最终为黑色，可得转移方程：
fu,i=[su=0]+∑v∈son(u)fv,i−1f_{u,i}=\left[s_u=0\right]+\sum_{v\in \text{son}(u)} f_{v,i-1}
两种情况取 min⁡\min 即可。
CPP
void dfs (int u)
{
	if (g[u].size () == 0)
	{
		f[u][0] = a[u];
		f[u][1] = !a[u];
		return ;
	}
	f[u][0] = a[u];
	for (int v : g[u]) dfs (v) , f[u][0] += f[v][0];
	for (int j = 1;j <= n;j ++)
	{
		int l1 = 0 , l2 = 0;
		for (int v : g[u]) l1 += f[v][j - 1] , l2 += f[v][j];
		f[u][j] = min (l1 + !a[u] , l2 + a[u]);
	}
}
可以使用 STL 优化以获取更多的分数。

优化

把 fu,if_{u,i} 看成一个图像 fu(x)f_u(x)，可以发现图像是一个凸包（因为最底层的 fuf_u 可以看作一个只有两个点的凸包，而凸包与凸包按位加也会是一个凸包）。设 ∑v∈son(u)fv,x\sum_{v\in \text{son}(u)} f_{v,x} 的图像为 F(x)F(x)， ∑v∈son(u)fv,x−1\sum_{v\in \text{son}(u)} f_{v,x-1} 的图像为 F′(x)F'(x)。如下图所示：
例如这是一个 F(x)F(x) 的图像，那么将其向右移一个单位长度即可变成 F′(x)F'(x) 的图像，如下：
设 (∑v∈son(u)fv,x)(x)(\sum_{v\in \text{son}(u)} f_{v,x})(x) 斜率为 00 的一段区间是 [L,R]\left[L,R\right]。接下来分成两种情况。

su=0s_u=0

此时 F′(x)F'(x) 的图像会向上一个单位长度，如图：
发现当 x≤Rx\le R 时 F(x)F(x) 会更小；否则，F′(x)F'(x) 更小。而形成的新图像则是 F(x)F(x) 在 RR 的位置插入了一条斜率为 11 的线段。

su=1s_u=1

此时 F(x)F(x) 的图像会向上一个单位长度，如图：
发现当 x≤Lx\le L 时 F(x)F(x) 会更小；否则，F′(x)F'(x) 更小。而形成的新图像则是 F(x)F(x) 在 LL 的位置添加了一条斜率为 −1-1 的线段。
那么就使用小根堆存储 fu(x)f_u(x) 对应图像每一位的斜率，在最后插入新线段即可。
F(x)F(x) 可以直接暴力合并，均摊复杂度 O(nlog⁡n)O(n\log n)。

答案

fu,0f_{u,0} 的值其实就是 uu 子树内的黑点数，用 fu,0f_{u,0} 加上所有负数斜率即为最小值。
AC CodeCPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5 , inf = 1e9 + 7;
int n , c[N] , f0[N];
bool a[N];
vector <int> g[N];
priority_queue <int , vector <int> , greater <int> > s[N] , q;
void dfs (int u)
{
	f0[u] = a[u] , c[u] = 0;
	for (int v : g[u])
	{
		dfs (v);
		f0[u] += f0[v];
		if (s[u].empty ()) swap (s[u] , s[v]) , c[u] = c[v];
		else
		{
			while (!q.empty ()) q.pop ();
			c[u] = 0;
			while (!s[u].empty () && !s[v].empty ())
			{
				int tmp = s[u].top () + s[v].top ();
				q.push (tmp);
				if (tmp < 0) c[u] += tmp;
				s[u].pop () , s[v].pop ();
			}
			s[u] = q;
		}
	}
	if (a[u]) s[u].push (-1) , c[u] --;
	else s[u].push (1);
}
signed main ()
{
	ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while (T --)
	{
		cin >> n;
		for (int i = 1;i <= n;i ++)
		{
			char op;
			cin >> op;
			a[i] = op - 48;
		}
		for (int i = 2;i <= n;i ++)
		{
			int p;
			cin >> p;
			g[p].push_back (i);
		}
		dfs (1);
		for (int i = 1;i <= n;i ++)
		{
			cout << f0[i] + c[i] << ' ';
			g[i].clear ();
			while (!s[i].empty ()) s[i].pop ();
		}
		cout << '\n';
	}
	return 0;
}

P11678 [USACO25JAN] Watering the Plants P

题意

有 nn 个水池，每次可以花费 wiw_i 的代价让第 ii 和第 i+1i + 1 个水池的水量加 11。求最小代价使第 ii 个水池中至少有 aia_i 的水量。

暴力

因为 ii 只能花 wi−1w_{i-1} 或 wiw_i 的贡献加水量，所以 wi−1w_{i-1} 和 wiw_i 的使用次数和不能小于 aia_i。
设 fi,jf_{i,j} 为前 i−1i-1 个水池已经锁定且满足条件，第 ii 个水池目前有 jj 水量的最小代价。可得转移方程：
fi,j=min⁡k≥ai−1−jfi−1,k+j×wi−1f_{i,j}=\min_{k\ge a_{i-1}-j}f_{i-1,k} + j \times w_{i-1}
现在如何从 fi−1(x)f_{i-1}(x) 快速转移到 fi(x)f_i(x) 就是要解决的问题了。

正解

考虑 Slope trick。
  • 可以发现，若 fi−1(x)f_{i-1}(x) 是下凸的，fi(x)f_i(x) 也是下凸的。
  • 证明：观察转移方程可以发现其实就是求了个后缀 min⁡\min，然后再加上一个一次函数。也就是把 fi−1(x)f_{i-1}(x) 每一对相邻点的斜率加上 wi−1w_{i-1}，因此还是下凸。
由于边界原因，i<3i < 3 时，fi(x)f_i(x) 不满足下凸性质。那么就可以先预处理出 fi,j(i<3)f_{i,j}(i<3)，然后再继续做。
接下来，设 LL 为 fi−1(x)f_{i-1}(x) 的最小值的位置，然后分两种情况讨论：
  • L≤ai−1L\le a_{i-1} 时，因为 LL 之后的斜率单调不下降，因此 fi(j)=fi−1(ai−1−j)+j×wi−1(j≤ai−1−L)f_i(j)=f_{i-1}(a_{i-1}-j)+j\times w_{i-1}(j\le a_{i-1}-L)；当 j>ai−1−Lj>a_{i-1}-L 时，fi(j)=fi−1(L)+j×wi−1f_i(j)=f_{i-1}(L)+j\times w_{i-1}。
  • L>ai−1L> a_{i-1} 时，因为 LL 之前的斜率单调下降，因此 fi−1(L)f_{i-1}(L) 为后缀的最小值，得 fi(j)=fi−1(L)+j×wi−1f_i(j)=f_{i-1}(L)+j\times w_{i-1}。
第一种情况可以看成把 fi−1(x)f_{i-1}(x) 中的 [L,ai−1][L,a_{i-1}] 这一段提取出来翻转后拼到 fi(x)f_i(x) 的前缀上，后面的推平成斜率为零 00 的直线。最后全局斜率加上 wi−1w_{i-1}。
第二种情况可以看成全局重置为一条斜率为 wi−1w_{i-1} 的直线，即全局推平然后全局斜率加上 wi−1w_{i-1}。
那如何维护斜率呢？考虑使用平衡树（FHQ Treap）。
维护三个操作：
  1. 区间翻转并区间取反（因为反转后斜率 kk 会变成 −k-k）。
  2. 区间推平为 00。
  3. 全局加 ww。
操作 11 可以参考文艺平衡树，在平衡树树上打标记，操作时下传标记。这个标记记为 tag1tag1，表示翻转并取反该子树。
操作 22，标记 tag2tag2 表示子树内的值全部清零。注意若打上了该标记，其他的 tagtag，该位的值以及子树和都要清 00。
操作 33 只需在根节点打上加的标记 tag3tag3，之后是一样的。
注意先下传顺序是操作 22，操作 33，操作 11。原因是 tag2tag2 标记时会把其他清零，若先下传另外两个会出问题；操作 33 是最后做的，只有下一次的下传可以影响，因此要在最后下传。
最后是求 fi,0f_{i,0}，根据转移式可得：
fi,0=min⁡k≥ai−1fi−1,kf_{i,0}=\min_{k\ge a_{i-1}}f_{i-1,k}
可以通过算前缀斜率和得到。
具体见代码。
AC CodeCPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10 , inf = 1e18 + 7;
mt19937 rd (time (0));
struct Node
{
	int l , r , w , sz;
	bool tag , mul;
	int val , sum , tsum;
} tr[N];
int id;
int get_new (int x , int w)
{
	tr[++ id] = {0 , 0 , rd () , 1 , 0 , 0 , w , w , 0};
	return id;
}
int rt;
void down (int p)
{
	swap (tr[p].l , tr[p].r);
	tr[p].tag = 0;
	tr[tr[p].l].tag ^= 1;
	tr[tr[p].r].tag ^= 1;
	tr[tr[p].l].val = -tr[tr[p].l].val;
	tr[tr[p].r].val = -tr[tr[p].r].val;
	tr[tr[p].l].tsum = -tr[tr[p].l].tsum;
	tr[tr[p].r].tsum = -tr[tr[p].r].tsum;
	tr[tr[p].l].sum = -tr[tr[p].l].sum;
	tr[tr[p].r].sum = -tr[tr[p].r].sum;
}
void dmul (int p)
{
	tr[p].mul = 0;
	tr[tr[p].l].mul = 1;
	tr[tr[p].r].mul = 1;
	tr[tr[p].l].tag = 0;
	tr[tr[p].r].tag = 0;
	tr[tr[p].l].tsum = 0;
	tr[tr[p].r].tsum = 0;
	tr[tr[p].l].sum = 0;
	tr[tr[p].r].sum = 0;
	tr[tr[p].l].val = 0;
	tr[tr[p].r].val = 0;
}
void dsum (int p)
{
	tr[tr[p].l].tsum += tr[p].tsum;
	tr[tr[p].r].tsum += tr[p].tsum;
	tr[tr[p].l].val += tr[p].tsum;
	tr[tr[p].r].val += tr[p].tsum;
	tr[tr[p].l].sum += tr[p].tsum * tr[tr[p].l].sz;
	tr[tr[p].r].sum += tr[p].tsum * tr[tr[p].r].sz;
	tr[p].tsum = 0;
}
void spl_w (int p , int x , int &l , int &r)
{
//	cout << p << endl;
	if (!p)
	{
		l = r = 0;
		return ;
	}
	if (tr[p].mul) dmul (p);
	if (tr[p].tag) down (p);
	if (tr[p].tsum) dsum (p);
	if (tr[p].val < x)
	{
		l = p;
		spl_w (tr[p].r , x , tr[p].r , r);
	}
	else
	{
		r = p;
		spl_w (tr[p].l , x , l , tr[p].l);
	}
	tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
	tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum + tr[p].val;
}
void spl (int p , int x , int &l , int &r)
{
	if (!p)
	{
		l = r = 0;
		return ;
	}
	if (tr[p].mul) dmul (p);
	if (tr[p].tag) down (p);
	if (tr[p].tsum) dsum (p);
	if (tr[tr[p].l].sz < x)
	{
		l = p;
		spl (tr[p].r , x - tr[tr[p].l].sz - 1 , tr[p].r , r);
	}
	else
	{
		r = p;
		spl (tr[p].l , x , l , tr[p].l);
	}
	tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
	tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum + tr[p].val;
}
int mrg (int l , int r)
{
	if (!l || !r) return l | r;
	if (tr[l].w <= tr[r].w)
	{
		if (tr[l].mul) dmul (l);
		if (tr[l].tag) down (l);
		if (tr[l].tsum) dsum (l);
		tr[l].r = mrg (tr[l].r , r);
		tr[l].sz = tr[tr[l].l].sz + tr[tr[l].r].sz + 1;
		tr[l].sum = tr[tr[l].l].sum + tr[tr[l].r].sum + tr[l].val;
		return l;
	}
	else
	{
		if (tr[r].mul) dmul (r);
		if (tr[r].tag) down (r);
		if (tr[r].tsum) dsum (r);
		tr[r].l = mrg (l , tr[r].l);
		tr[r].sz = tr[tr[r].l].sz + tr[tr[r].r].sz + 1;
		tr[r].sum = tr[tr[r].l].sum + tr[tr[r].r].sum + tr[r].val;
		return r;
	}
}
void rev (int p)
{
	tr[p].tag ^= 1;
	tr[p].val = -tr[p].val;
	tr[p].sum = -tr[p].sum;
	tr[p].tsum = -tr[p].tsum;
}
void clr (int p)
{
	tr[p].mul = 1;
	tr[p].tag = 0;
	tr[p].sum = 0;
	tr[p].tsum = 0;
	tr[p].val = 0;
}
int N_ , q;
void work (int l , int r , int w)
{
	int ll , rl , rr;
	spl (rt , l - 1 , ll , rl);
	spl (rl , r - l + 1 , rl , rr);
	clr (ll);
	clr (rr);
	rev (rl);
	rt = mrg (mrg (rl , rr) , ll);
	tr[rt].tsum += w;
	tr[rt].sum += tr[rt].sz * w;
	tr[rt].val += w;
}
void ins (int x , int w , int &rt)
{
	rt = mrg (rt , get_new (x , w));
}
int fsum (int r)
{
	int p = rt , ans = 0;
	while (p)
	{
		if (tr[p].mul) dmul (p);
		if (tr[p].tag) down (p);
		if (tr[p].tsum) dsum (p);	
		if (tr[tr[p].l].sz < r)
			ans += tr[tr[p].l].sum + tr[p].val , r -= tr[tr[p].l].sz + 1 , p = tr[p].r;
		else
			p = tr[p].l;
	}
	return ans;
}
int n , m , a[N] , w[N] , g[N];
int f[3][N];
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	cin >> n;
	m = 1e6 + 2;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	for (int i = 1;i < n;i ++) cin >> w[i];
	memset (f[0] , 0x3f , sizeof f[0]);
	f[0][0] = 0;
	for (int i = 1;i <= 2;i ++)
	{
		int ans = inf , minn = inf;
		for (int j = a[i];j <= m;j ++)
			ans = min (ans , f[i - 1][j]);
		for (int j = 0;j <= m;j ++)
		{
			if (a[i] >= j) ans = min (ans , f[i - 1][a[i] - j]);
			f[i][j] = ans + j * w[i];
			if (j >= a[i + 1])
				minn = min (minn , f[i][j]);
		}
		cout << minn << '\n';
	}
	int lst = f[2][a[3]];
	for (int i = 1;i <= m;i ++)
	{
		ins (i , f[2][i] - f[2][i - 1] , rt);
		if (i >= a[3]) lst = min (f[2][i] , lst);
	}
	for (int i = 4;i <= n;i ++)
	{
		int ll , lr;
		spl_w (rt , 0 , ll , lr);
		int ans = tr[ll].sz + 1;
		rt = mrg (ll , lr);
		if (a[i - 1] >= ans) work (ans , a[i - 1] , w[i - 1]);
		else
		{
			clr (rt);
			tr[rt].tsum += w[i - 1];
			tr[rt].sum += tr[rt].sz * w[i - 1];
			tr[rt].val += w[i - 1];
		}
		spl_w (rt , 0 , ll , lr);
		ans = tr[ll].sz;
		rt = mrg (ll , lr);
		if (a[i] >= ans) lst += fsum (a[i]);
		else lst += fsum (ans);
		cout << lst << '\n';
	}
	return 0;
}

评论

共 10 条评论，欢迎与作者交流。

正在加载评论...