斜率优化学习报告_斜率优化的另一种方式

考虑到剩下的时间要练几套联赛题，如果平衡树没有理解到能够写学习报告的水平，这个估计就是联赛之前最后一篇学习报告了。

斜率优化的原理

前置知识

决策单调性

其实斜率优化是决策单调性优化dp的一个子问题，我之前试着花了一天来学习决策单调性，这样学习报告写的能更有逻辑一点，结果几乎没学明白什么东西，确实不好理解。好在斜率优化中用到的决策单调性只到理解基础概念就够了。以及这里的定义不是很严谨，理解精神（

首先，对于一个点$i$，能够用来更新$i$的点（以下以$f_i$为例说明）称为i的决策点，在这些点中，能够使$f_i$取得最优情况的点即为最优决策点，记为$g_i$。如果$g_i$随着$i$的单调变化而单调变化，称此时$f_i$具有决策单调性。
问题就在于怎么判断一个函数是否具备决策单调性，显然不能用实际求解判断，这时候就用到一个叫四边形不等式的东西。
四边形不等式内容如下：
$\forall 1\le i_1\le i_2\le n,1\le j_1\le j_2\le m,f_{i_1,j_i}+f_{i_2,j_2}\le f_{i_1,j_2}+f_{i_2,j_1}$，则$f$满足四边形不等式。
进一步地，四边形不等式判定定理如下：
$\forall 1\le i<n,1\le j<m,f_{i,j}+f_{i+1,j+1}<f_{i,j+1}+f_{i+1,j}$，则$f$满足四边形不等式。
当一个函数满足四边形不等式时，该函数具有决策单调性。
清楚这些基本概念和操作，就足以应对斜率优化了。

斜率优化的适用情况

首先回忆一下单调队列问题的$dp$，大概长成这样：
d p i = m a x { F ( j ) + G ( k ) } dp_i=max\{F(j)+G(k)\} dpi​=max{F(j)+G(k)}
其中$j$有一定的取值范围，$k$表示与$j$无关的部分。当这个取值范围的变化随着$i$单调变化而单调变化的时候，就可以平行的用队列维护这个取值区间。

理解单调队列核心原理最好的模型我认为是滑动窗口，没有之一。

单调队列在应用的时候，把一维的枚举变成了唯一点，为此，需要保证队列中的决策点的对应函数值只与这个决策点有关，否则就不知道哪一个决策点是最优的，例如形如 d p i = m a x { F ( i ) G ( j ) } dp_i=max\{F(i)G(j)\} dpi​=max{F(i)G(j)}的式子，决策点会随着$i$的变化而变化，这时候队列就不能维护出最优决策点了。
不过此时决策点也是只受当前点影响的，对于这种情况，就用到了斜率优化。

斜率优化

首先设转移式 f i = m i n { f j − s i × s j } + c f_i=min\{f_j-s_i\times s_j\}+c fi​=min{fj​−si​×sj​}+c，其中$s$随$i$递增。
对于一个点$i$，考虑它的两个决策点$j$和$k$，$j>k$，假设$j$优于$k$，那么$f_j-s_i\times s_j<f_k-s_i\times s_k$.
为了计算两个决策点之间的关系，把当前点$i$提取出来，式子变形为$f_j-f_k<s_i(s_j-s_k)$，进一步可得$\frac{f_j-f_k}{s_j-s_k}<s_i$。

注意：在对点斜式进行进一步变形的时候，一定要考虑变号的问题！

此时就得出判断哪一个更优的方法：当决策点$j$和$k$形成直线的斜率小于$s_i$时，$j$更优。推广一下，假设有三个点$j$,$k$,$l$ 满足 $j>k>l$，三点两两形成的直线斜率都小于$s_i$，那么$j$优于$k$优于$l$，而斜率大于$s_i$时结论恰好相反。
因此，假设有这么一个下凸壳（一个凸多边形的下部），如果要找一个最优决策点，应该是其中第一个斜率大于$s_i$的线段的左端点。另外，对于这个情境，$s_i$随着$i$递增，所以每一次的最优决策点会逐渐右移，这时候决策点又一次随着$i$单调变化了，于是就可以用类似于单调队列的方法维护决策点。

维护凸壳的方式

上面提到的仅仅是一种情况，实际上，维护方式受横坐标和最优决策点（或者说是最优决策斜率）两个因素影响。
从例子当中提到的最简单的单调队列维护下凸壳开始，这种方法的具体实现过程有三步：
1 删掉所有斜率小于等于当前最优决策斜率的线段，因为根据上面的分析，小于等于当前最优决策斜率的直线以后也不可能用到了。
2 更新当前点函数值
3 加入当前点，如果当前点和末尾的点斜率不大于最后一条线段，就把最后一条线段删掉，一直删到大于为止。
现在忽略2，剩下两步更新平均复杂度是$O(1)$的，原因有二，一是最优决策斜率单调，二是一定与末尾比较，即横坐标单调。

注意：这里的横坐标和下标不是一回事，对于这个例子，横坐标是$s_i$

那么现在要讨论的就是剩下的情况。

假设最优决策斜率不单调，那么此时需要寻找最优决策点，也就是肯定不能删除队首。但是队尾仍然是可以删除维护凸壳的，这方面最好画一个图理解：

假设A和C是原来下凸壳上的点，加入一个点B使得$k_{AC}>k_{BC}$，可以发现，任意一条直线从下向上扫，一定先经过A或B，即取得最小截距的点一定不是C。在原问题当中，这个意义就变为决策点C一定更差，所以仍然可以删去。
在这种情况下，维护下凸壳仍然利用队尾删除，寻找决策点则是利用二分，考虑到这里不更新队头，这种方法实际也可以叫二分+单调栈。

二分+单调栈在决策单调性这个大的主题当中同样是一种非常重要的方法。

假设横坐标不单调，那么在加入当前点的时候，这个点就可能出现在中间，也就是必须向左右都进行删点才能完成维护。维护的大致方法其实同上，向两侧删除，直到左侧的斜率小于新加入的斜率，右侧的斜率大于新加入的斜率。另外，点有可能加入到下凸壳内部，这时左侧斜率大于右侧斜率，直接删除这个点。如图：

（图中蓝色点为原来凸壳上的点，橙色点为两次新加入的当前点，红色边为加入L点时要删除的边）
上述过程需要寻找斜率的前驱和后继，所以是利用Splay维护的。

以下通过几道题总结这三种方法的写法和其中的一些细节。

对于斜率优化更多的入门介绍，推荐洛谷P3195玩具装箱题解的前两篇，一篇简单明了，另一篇论证严密。此题本身也是非常好的入门题。

例题

单调队列法

T1 特别行动队（洛谷P3628 ，难度3）
此题实现很基础，主要是练习一下推导点斜式。
设$f_i$表示把$i$分入队后的最大战斗力之和，首先设计$O(n^2)dp$，设$x_i$的前缀和为$s_i$，则转移式为 f i = m a x { f j + a ( s i − s j ) 2 + b ( s i − s j ) } + c f_i=max\{f_j+a(s_i-s_j)^2+b(s_i-s_j)\}+c fi​=max{fj​+a(si​−sj​)2+b(si​−sj​)}+c.
转移式中存在同时与$i,j$有关的项，进行斜率优化。
设两个决策点$j,k$，$j>k$且$j$优于$k$，变形过程如下：
f j + a ( − 2 s i s j + s j    2 ) − b s j > f k + a ( − 2 s i s k + s k    2 ) − b s k ⇒ ( f j + s j    2 ) − ( f k + s k    2 ) > 2 a s i ( s j − s k ) ⇒ ( f j + s j    2 ) − ( f k + s k    2 ) ( s j − s k ) > 2 a s i

$$\begin{aligned} f_j+a(-2s_is_j+s_j^{\,\,2})-bs_j&>f_k+a(-2s_is_k+s_k^{\,\,2})-bs_k\\ \Rightarrow (f_j+s_j^{\,\,2})-(f_k+s_k^{\,\,2})&>2as_i(s_j-s_k)\\ \Rightarrow\frac{(f_j+s_j^{\,\,2})-(f_k+s_k^{\,\,2})}{(s_j-s_k)}&>2as_i \end{aligned}$$ fj​+a(−2si​sj​+sj2​)−bsj​⇒(fj​+sj2​)−(fk​+sk2​)⇒(sj​−sk​)(fj​+sj2​)−(fk​+sk2​)​​>fk​+a(−2si​sk​+sk2​)−bsk​>2asi​(sj​−sk​)>2asi​​
此题中，横坐标为$s$，纵坐标为$f+s^2$，最优决策斜率为$2as$.考虑到推导出的式子是大于时成立，且$2a{s}_i$随着$i$递增而递减，所以利用单调队列维护上凸壳。

在斜率优化中，除了移项带来的变号以外，基本上只关心变化趋势，不关心具体正负。

先上代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read_int(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
inline long long read_long(){
	long long x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}

const int N = 1e6 + 1;
long long sum[N],f[N],a,b,c;
int front,rear,Q[N];
long long X(int i){
	return sum[i];//调用函数时间常数大，建议换成#define
}
long long Y(int i){
	return f[i] + a * sum[i] * sum[i];
}
long long val(long long x){
	return a * x * x + b * x + c;
}
int main(){
	int i,n;
	long long k;
	n = read_int();
	a = read_long(),b = read_long(),c = read_long();
	for(i = 1;i <= n;i++){
		sum[i] = read_long();
		sum[i] += sum[i - 1];
	}
	for(i = 1;i <= n;i++){
		k = 2 * a * sum[i] + b;
		while(front < rear && Y(Q[front + 1]) - Y(Q[front]) >= k * (X(Q[front + 1]) - X(Q[front]))) ++front;
		f[i] = f[Q[front]] + val(sum[i] - sum[Q[front]]);
		while(front < rear && (Y(Q[rear]) - Y(Q[rear - 1])) * (X(i) - X(Q[rear])) <= (Y(i) - Y(Q[rear])) * (X(Q[rear]) - X(Q[rear - 1]))) --rear;
		Q[++rear] = i;
	}
	printf("%lld\n",f[n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

斜率的计算

显然比较斜率的时候，用乘法代替除法精度更高（记得考虑乘法会不会爆long long），而且往往不需要考虑斜率不存在的情况。如果使用除法一定要先判断是否不存在斜率然后计算，为了精度可以开long double或者手动卡精度。

卡精度就是一个比较玄学的东西了，网上细讲卡精度的非常少，看了一圈，基本就得到这么两条信息：比较两个浮点数$x,y$，设精度为$eps$（一般是$10^{-8}-10^{-10}$之间），$x=y$ 转化为 $fabs(x-y)\le eps$，$x>y$ 转化为 $x\ge y+eps.$
综上所述，最好少用除法形式比较斜率。

队列维护

去重主要问题出现在队尾更新，也是一个玄学问题，大部分时候建议带等号比较（也就是斜率相等也要删除）。
另外，斜率优化要求队列里面有两个点（否则没法形成直线），所以更新条件一定是front<rear.

T2 征途（洛谷P4072，难度3.5）
这题相比T1，多出来那0.5完全是因为方差。
上来先化简方差公式：
s 2 = 1 m ∑ i = 1 m ( x i − x ˉ ) 2 = 1 m ∑ i = 1 m ( x i − 1 m ∑ j = 1 m x j ) 2 = 1 m ( ∑ i = 1 m x i    2 + m m 2 ( ∑ i = 1 m x i ) 2 − 2 × 1 m ( ∑ i = 1 m x i ) 2 ) = 1 m ∑ i = 1 m x i    2 − 1 m 2 ( ∑ i = 1 m x i ) 2 ∴ s 2 × m = m ∑ i = 1 m x i    2 − ( ∑ i = 1 m x i ) 2

$$\begin{aligned} s^2&=\frac{1}{m}\sum_{i=1}^{m}(x_i-\bar x)^2\\ &=\frac{1}{m}\sum_{i=1}^{m}(x_i-\frac{1}{m}\sum_{j=1}^{m}x_j)^2\\ &=\frac{1}{m}(\sum_{i=1}^{m}x_i^{\,\,2}+\frac{m}{m^2}(\sum_{i=1}^{m}x_i)^2-2\times\frac{1}{m}(\sum_{i=1}^{m}x_i)^2)\\ &=\frac{1}{m}\sum_{i=1}^{m}x_i^{\,\,2}-\frac{1}{m^2}(\sum_{i=1}^{m}x_i)^2\\ \therefore s^2\times m&=m\sum_{i=1}^{m}x_i^{\,\,2}-(\sum_{i=1}^{m}x_i)^2 \end{aligned}$$ s2∴s2×m​=m1​i=1∑m​(xi​−xˉ)2=m1​i=1∑m​(xi​−m1​j=1∑m​xj​)2=m1​(i=1∑m​xi2​+m2m​(i=1∑m​xi​)2−2×m1​(i=1∑m​xi​)2)=m1​i=1∑m​xi2​−m21​(i=1∑m​xi​)2=mi=1∑m​xi2​−(i=1∑m​xi​)2​
后面的那一项就是一个和的平方，是定值，影响答案的是前面的平方和。因此设$f_{i,k}$表示到第$k$天走完第$i$段路的最小平方和，设前缀和为$s_i$，有 f i , k = m i n { f j , k − 1 + ( s i − s j ) 2 } . f_{i,k}=min\{f_{j,k-1}+(s_i-s_j)^2\}. fi,k​=min{fj,k−1​+(si​−sj​)2}.
变形的方法完全同前，最终横坐标为$s$，纵坐标为$f+s^2$，斜率为$s$.
考虑到这题是多维的，可以用滚动数组节约空间，初始化的时候要清空队列。此题当中$i<k$的部分没有意义，所以可以压缩一点常数。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read_int(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
inline long long read_long(){
	long long x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}

const int N = 3001;
int front,rear,Q[N];
long long f[N][2],sum[N];
long long Y(int i){
	return f[i][0] + sum[i] * sum[i];
}
int main(){
	int i,j,n,m;
	n = read_int(),m = read_int();
	for(i = 1;i <= n;i++){
		sum[i] = read_long();
		sum[i] += sum[i - 1];
	}
	memset(f,0x3f,sizeof(f));//初始化是必要的！
	f[0][1] = 0; //注意滚动数组的初始化
	for(i = 1;i <= m;i++){
		for(j = 0;j <= n;j++) f[j][0] = f[j][1],Q[j] = 0;
		Q[1] = i - 1;
		front = rear = 1;
		for(j = i;j <= n;j++){
			while(front < rear && Y(Q[front + 1]) - Y(Q[front]) <= 2 * sum[j] * (sum[Q[front + 1]] - sum[Q[front]])) ++front;
			f[j][1] = f[Q[front]][0] + (sum[j] - sum[Q[front]]) * (sum[j] - sum[Q[front]]);
			while(front < rear && (Y(Q[rear]) - Y(Q[rear - 1])) * (sum[j] - sum[Q[rear]]) >= (Y(j) - Y(Q[rear])) * (sum[Q[rear]] - sum[Q[rear - 1]])) --rear;
			Q[++rear] = j;
		}
	}
	printf("%lld\n",m * f[n][1] - sum[n] * sum[n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

斜率优化即使是优化，也是在dp的基础上优化，所以正常dp有的初始化和去除不存在情况的方法仍然适用于斜率优化。

二分法

T3 任务安排（洛谷P2365，难度3.5）
此题多的0.5完全是因为数据强度。
设$f_i$表示完成前$i$个任务花费的最少费用，前缀和形式同前。由于每一段还要额外加上完成时间造成的费用，采取反向思维，不如计算一个任务会使得多少其他任务的完成时间增加。
那么转移式就是 f i = m i n { f j + s t i ( s c i − s c j ) + S ( s c n − s c j ) } . f_i=min\{f_j+st_i(sc_i-sc_j)+S(sc_n-sc_j)\}. fi​=min{fj​+sti​(sci​−scj​)+S(scn​−scj​)}.

一开始觉得比较难想，后来意识到，这个$O(n^2)$不就是排队接水的思维吗？

变形后，纵坐标为$f$，横坐标为$sc$，最优决策斜率为$S+st$.考虑到这个加强版的$t_i$可能为负，所以最优决策斜率没有单调性，此题需要二分找最优决策点。再次复习一遍：最优决策点是取到最优决策斜率的后继的线段的左端点。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read_int(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
inline long long read_long(){
	long long x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}

const int N = 3e5 + 1;
int n,Q[N],front,rear;
long long s,f[N],sumc[N],sumt[N];
long long X(int i){
	return sumc[i];
}
long long Y(int i){
	return f[i];
}
int find(int x){
	int l = front,r = rear,mid;
	if(l == r) return front;
	while(l < r){
		mid = (l + r) >> 1;
		if(Y(Q[mid + 1]) - Y(Q[mid]) < (sumt[x] + s) * (X(Q[mid + 1]) - X(Q[mid]))) l = mid + 1;
		//此处是否取等不影响答案，我认为是由于维护队尾已经去重了
		else r = mid;
	}
	return l;
}
int main(){
	int i,j,temp;
	n = read_int(),s = read_long();
	for(i = 1;i <= n;i++){
		sumt[i] = read_long(),sumc[i] = read_long();
		sumt[i] += sumt[i - 1],sumc[i] += sumc[i - 1];
	}
	memset(f,0x3f,sizeof(f));
	f[0] = 0;
	for(i = 1;i <= n;i++){
		temp = find(i);
		f[i] = f[Q[temp]] + sumt[i] * (sumc[i] - sumc[Q[temp]]) + s * (sumc[n] - sumc[Q[temp]]);
		while(front < rear && (Y(Q[rear]) - Y(Q[rear - 1])) * (X(i) - X(Q[rear])) >= (Y(i) - Y(Q[rear])) * (X(Q[rear]) - X(Q[rear - 1]))) --rear;
		Q[++rear] = i;
	}
	printf("%lld\n",f[n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

Splay法

T4 基站建设（洛谷P2497，难度4）
这题难度1分给Splay。
首先，这题并没有给$r2$，需要自己求最小值。显然，两个基站间建立连接的最小花费出现在一个的发射范围和另一个的接受范围相切的时候。

Geogebra真好用

假设传递过程为$\odot A\to \odot C$，那么根据勾股定理，有$(r_{1_A}+r_{2_C}{)}^2=(r_{2_C}-r_{1_A}{)}^2+(x_C-x_A{)}^2$，化简之后打根号，算出传递的费用为$\frac{x_C-x_A}{2\sqrt{r_j}}$.那么设$f_i$为$i$接受信号的最小话费， f i = m i n { f j + x i − x j 2 r j } + v i . f_i=min\{f_j+\frac{x_i-x_j}{2\sqrt{r_{j}}}\}+v_i. fi​=min{fj​+2rj​ ​xi​−xj​​}+vi​.
考虑到这个形式确实奇特，写一下变形的过程：
f j + x i − x j 2 r j < f k + x i − x k 2 r k ⇒ ( f j − x j 2 r j ) − ( f k − x k 2 r k ) < x i ( 1 2 r k − 1 2 r j ) ⇒ ( f j − x j 2 r j ) − ( f k − x k 2 r k ) − 1 2 r j − ( − 1 2 r k ) < x i

$$\begin{aligned} f_j+\frac{x_i-x_j}{2\sqrt{r_{j}}}&<f_k+\frac{x_i-x_k}{2\sqrt{r_{k}}}\\ \Rightarrow (f_j-\frac{x_j}{2\sqrt{r_j}})-(f_k-\frac{x_k}{2\sqrt{r_k}})&<x_i(\frac{1}{2\sqrt{r_k}}-\frac{1}{2\sqrt{r_j}})\\ \Rightarrow \frac{(f_j-\frac{x_j}{2\sqrt{r_j}})-(f_k-\frac{x_k}{2\sqrt{r_k}})}{-\frac{1}{2\sqrt{r_j}}-(-\frac{1}{2\sqrt{r_k}})}&<x_i \end{aligned}$$ fj​+2rj​ ​xi​−xj​​⇒(fj​−2rj​ ​xj​​)−(fk​−2rk​ ​xk​​)⇒−2rj​ ​1​−(−2rk​ ​1​)(fj​−2rj​ ​xj​​)−(fk​−2rk​ ​xk​​)​​<fk​+2rk​ ​xi​−xk​​<xi​(2rk​ ​1​−2rj​ ​1​)<xi​​
这里之所以没有讨论是否需要变号，是因为横坐标$-\frac{1}{2\sqrt{r}}$本身就没有单调性，所以讨论变号意义不大，不过从点斜式符号上可知这题维护的是下凸壳。由于横坐标没有单调性，要用Splay维护。

在维护之前，再次确认一遍用到的功能：查询斜率的前驱和后继，插入点，询问最优转移斜率。
从目的上，平衡树的左右儿子区分（维护依据）看横坐标，树上点权为下标，除了基本的信息，还要维护对应点的横纵坐标、到左右第一个点的斜率（注意不是到左右儿子的斜率）。
首先是一些基础的操作，与一般的Splay一样：

int add(double x,double y,int c,int fa){
		val[++tot] = c;
		f[tot] = fa;
		son[tot][0] = son[tot][1] = 0;
		xx[tot] = x,yy[tot] = y;
		return tot;
	}
	bool isright(int now){
		return son[f[now]][1] == now;
	}
	void rotate(int now){
		int fa = f[now],anc = f[fa],k = isright(now);
		int temp = son[now][k ^ 1];
		f[temp] = fa,son[fa][k] = temp;
		f[now] = anc;
		if(anc) son[anc][isright(fa)] = now;
		f[fa] = now,son[now][k ^ 1] = fa;
	}
	void splay(int now,int goal){
		for(int fa;(fa = f[now]) != goal;rotate(now)){
			if(f[fa] != goal){
				if(isright(fa) == isright(now)) rotate(fa);
				else rotate(now);
			}
		}
		if(!goal) rt = now;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

然后是前驱和后继，以前驱为例，先求一下询问点（提前移动到根）到左儿子的斜率，如果比原来左儿子向左的斜率更大，说明插入已经合法了，记录这个点，继续向它的右儿子移动，否则继续向左儿子移动，如此反复。后继则刚好相反。

int query_pre(){
		int now = son[rt][0],ret = 0;
		while(now){
			if(lk[now] < slope(now,rt)){
				ret = now,now = son[now][1];
			}
			else now = son[now][0];
		}
		return ret;
	}
	int query_nxt(){
		int now = son[rt][1],ret = 0;
		while(now){
			if(rk[now] > slope(now,rt)){
				ret = now,now = son[now][0];
			}
			else now = son[now][1];
		}
		return ret;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

由于在树上维护，这里就不得不用除法求斜率了。

完成这几个基本功能就可以插入点了。
空树和插入新点的过程其实和一般平衡树是一样的，不同的是需要更新插入点到左右最近的点的斜率，以左侧为例，先求前驱，然后把前驱旋转到插入点的左儿子上，这时它的右儿子就是需要从凸壳当中删除的点集，直接把右儿子赋为0就行了，然后更新插入点的左侧斜率。右侧正好相反。
最后是特判插入点在凸壳内的情况，因为要先求左右侧的斜率，所以这个在最后进行（考虑到维护原理，不用担心这种非法情况在求斜率的时候破坏原有凸壳的问题）。操作并不复杂，直接把左右儿子取出来，把左儿子的右儿子变成自己的右儿子，再恢复一下斜率就行了。注意此时它是根节点，所以要把根节点的位置传给左儿子。
整个插入部分如下：

void insert(double x,double y,int c){
		if(!rt){
			rt = add(x,y,c,0);
			lk[rt] = -1e18,rk[rt] = 1e18;
			return;
		}
		int now = rt;
		while(1){
			if(son[now][x > xx[now]]) now = son[now][x > xx[now]];
			else{
				son[now][x > xx[now]] = add(x,y,c,now);
				splay(tot,0);
				break;
			}
		}
		//插入点
		now = rt;
		if(son[now][0]){
			int temp = query_pre();
			splay(temp,now);
			son[temp][1] = 0;
			lk[now] = rk[temp] = slope(temp,now);
		}
		else lk[now] = -1e18;
		if(son[now][1]){
			int temp = query_nxt();
			splay(temp,now);
			son[temp][0] = 0;
			rk[now] = lk[temp] = slope(temp,now);
		}
		else rk[now] = 2e18;
		//求斜率，维护凸壳
		if(lk[now] > rk[now]){
			int ls = son[now][0],rs = son[now][1];
			f[ls] = 0,rt = ls;
			son[ls][1] = rs,f[rs] = ls;
			lk[rs] = rk[ls] = slope(ls,rs);
		}
		//特判
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

对于询问，就一直寻找一个点使得其左侧斜率小于等于最优决策斜率且右侧斜率大于等于最优决策斜率就行了。如果左侧斜率也大于最优斜率就去左儿子找（这里直接用下凸壳斜率单调递增理解，不要结合图像 ，更容易错，别问我为什么知道 ）。

int query(double x){
		int now = rt;
		while(1){
			if(!now) return 0;
			if(lk[now] <= x && x <= rk[now]) return val[now];
			else if(lk[now] > x) now = son[now][0];
			else now = son[now][1];
		}
	}
1
2
3
4
5
6
7
8
9

主函数就很简单了，每次询问之后插入当前点就可以了。

int main(){
	int i,j;
	double res = 1e18;
	scanf("%d %lf",&n,&m);
	for(i = 1;i <= n;i++){
		scanf("%lf %lf %lf",&pos[i],&r[i],&v[i]);
	}
	dp[1] = v[1];//预处理，记得有特殊点插入特殊点，没有可以不必插入0
	bt.insert(X(1),Y(1),1);
	for(i = 2;i <= n;i++){
		j = bt.query(pos[i]);
		dp[i] = dp[j] + (pos[i] - pos[j]) / (2.0 * sqrt(r[j])) + v[i];
		//printf("%lf %lf %lf\n",pos[i] - pos[j],2.0 * sqrt(r[j]),(pos[i] - pos[j]) / (2.0 * sqrt(r[j])));
		bt.insert(X(i),Y(i),i);
		if(pos[i] + r[i] >= m) res = min(res,dp[i]);
	}
	printf("%.3lf\n",res);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

T5 货币兑换（难度4.5）
这题难度1分给Splay，0.5分给数据。

一个对于开场想dp的人不太好想的一个贪心：如果$x$日买而$y$日卖收益最大，最好的方案就是在$x$天把前全部拿去买，在$y$天全部卖掉。

不要在这个地方纠结这个$x$怎么取，这个是优化的内容，不是思路的内容。这种问题是一个贪心和dp同时存在的时候我经常遇到的问题，即混淆贪心和dp的部分。所以一定要在贪心思路出现之后考虑枚举的内容，以防把dp做成贪心浪费时间。

设$f_i$表示在第$i$天获得的最多金钱，那么花掉这些钱购买金券，能买到$\frac{r_i{f}_i}{a_i{r}_i+b_i}$张A券，$\frac{f_i}{a_i{r}_i+b_i}$张B券（这个计算相当容易出错 ，起码我一开始算错了 ）。设后者为$x_i$，前者即为$r_i{x}_i$，那么转移式就可以写成 f i = m a x { f j + a i r j x j + b i x j } f_i=max\{f_j+a_ir_jx_j+b_ix_j\} fi​=max{fj​+ai​rj​xj​+bi​xj​}，变形后横坐标为$x$，纵坐标为$rx$，斜率为$-\frac{b}{a}$，同上，这个横坐标没有单调性，所以需要用Splay维护上凸壳。思路和前面一样，和斜率有关的全部反过来。但是此题数据卡精度，long double都不好使，需要手动调精度。
Splay部分如下：

#define eps 1e-9
struct yjx{
	int rt,tot,son[N][2],f[N],val[N];
	double xx[N],yy[N],lk[N],rk[N];
	int add(double x,double y,int c,int fa){
		val[++tot] = c;
		son[tot][0] = son[tot][1] = 0,f[tot] = fa;
		xx[tot] = x,yy[tot] = y;
		return tot;
	}
	bool isright(int now){
		return son[f[now]][1] == now;
	}
	void rotate(int now){
		int fa = f[now],anc = f[fa],k = isright(now);
		int temp = son[now][k ^ 1];
		f[temp] = fa,son[fa][k] = temp;
		f[now] = anc;
		if(anc) son[anc][isright(fa)] = now;
		f[fa] = now,son[now][k ^ 1] = fa;
	}
	void splay(int now,int goal){
		for(int fa;(fa = f[now]) != goal;rotate(now)){
			if(f[fa] != goal){
				if(isright(now) == isright(fa)) rotate(fa);
				else rotate(now);
			}
		}
		if(!goal) rt = now;
	}
	double slope(int i,int j){
		return (yy[i] - yy[j]) / (xx[i] - xx[j]);
	}
	int query_pre(){
		int now = son[rt][0],ret = 0;
		while(now){
			if(lk[now] + eps >= slope(now,rt)){
				ret = now,now = son[now][1];
			}
			else now = son[now][0];
		}
		return ret;
	}
	int query_nxt(){
		int now = son[rt][1],ret = 0;
		while(now){
			if(rk[now] <= slope(now,rt) + eps){
				ret = now,now = son[now][0];
			}
			else now = son[now][1];
		}
		return ret;
	}
	void insert(double x,double y,int c){
		if(!rt){
			rt = add(x,y,c,0);
			lk[tot] = 1e18,rk[tot] = -1e18;
			return;
		}
		int now = rt;
		while(1){
			if(son[now][x + eps >= xx[now]]) now = son[now][x + eps >= xx[now]];
			else{
				son[now][x + eps >= xx[now]] = add(x,y,c,now);
				splay(tot,0);
				break;
			}
		}
		now = rt;
		if(son[now][0]){
			int temp = query_pre();
			splay(temp,now);
			son[temp][1] = 0;
			lk[now] = rk[temp] = slope(temp,now);
		}
		else lk[now] = 1e18; 
		if(son[now][1]){
			int temp = query_nxt();
			splay(temp,now);
			son[temp][0] = 0;
			rk[now] = lk[temp] = slope(temp,now);
		}
		else rk[now] = -1e18;
		if(lk[now] <= rk[now] + eps){
			int ls = son[now][0],rs = son[now][1];
			f[ls] = 0,rt = ls;
			son[ls][1] = rs,f[rs] = ls;
			lk[rs] = rk[ls] = slope(ls,rs);
		}
	}
	int query(double x){
		int now = rt;
		while(1){
			if(!now) return 0;
			if(lk[now] + eps >= x && x + eps >= rk[now]) return val[now];
			else if(lk[now] < x) now = son[now][0];
			else now = son[now][1];
		}
	}
}bt;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

存在特殊限制的问题

T6 回家路线（洛谷P6302，难度5）
一道除了斜率优化本身以外全都难的题。

似乎是学习报告里面第一个难度5.

首先这题如果以时间或者站点为一维状态难以设计，所以把列车编号当下标，设$f_i$表示乘上第$i$班列车的最小烦躁值，那么有 f i = m i n { f j + ( p i − q j ) 2 } f_i=min\{f_j+(p_i-q_j)^2\} fi​=min{fj​+(pi​−qj​)2}.经过变形之后最优决策点与$p$有关，横坐标也是$p$（其实看原始式子可以观察出来），所以先按照$p$排序，就满足单调队列维护的条件了。
这个设计成斜率优化毫无难度，关键是这题有两个限制，一是$y_j=x_i$，二是$p_i>q_j$。对于前者，可以开多个队列，保证每一个$i$只从对应的队列存储的决策点更新。对于后者，也可以开多个vector，保证每一个$p_i$只从对应的$q_j$更新（因为先更新$j$后更新$i$）。
由于时间是枚举的，所以在每一个时间点，先把$q$等于当前时间的$y$更新对应的队列的队尾，然后枚举$p$等于当前时间的$x$，删除队首进行更新。这里顺便应用的是桶排给$p$排序，所以现在一共是三个vector，id下标为p存储下标，buc下标为q存储下标，Q下标为y存储决策点下标。

这个逻辑真的对于一道dp相当混乱，我不得不把定义写到纸上注释到代码里面才能往下写代码…

另外就是一些vector的性质带来的问题，比如访问越界，需要先判断是否超过了vector的大小，然后再判断是push_back还是直接修改。对于只有一个点的vector应该直接把决策点手动赋值为0，空vector不操作。
总之，此题的更新思路不但复杂而且也没有那么模版化的更新顺序。我只能说不愧为NOI2019.
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
inline int read_int(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
inline long long read_long(){
	long long x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}

const int N = 1e6 + 1;
const int M = 1e5 + 1;
int n,m,x[N],y[N];
long long t,a,b,c,p[N],q[N],front[M],rear[M],f[N];
vector<int> buc[M],id[M],Q[M];
//id下标为p存储下标，buc下标为q存储下标，Q下标为点存储决策点下标
long long Y(int i){
	return f[i] + a * q[i] * q[i] - b * q[i];
}
int main(){
	int i,j,k,pos,temp;
	long long res = 1e18;
	n = read_int(),m = read_int(),a = read_long(),b = read_long(),c = read_long();
	for(i = 1;i <= m;i++){
		x[i] = read_int(),y[i] = read_int(),p[i] = read_long(),q[i] = read_long();
		id[p[i]].push_back(i);
		t = max(t,q[i]);
	}
	for(i = 1;i <= n;i++) rear[i] = -1;
	for(i = 0;i <= t;i++){
		for(j = 0;j < (int)buc[i].size();j++){
			pos = buc[i][j],k = y[pos];
			while(front[k] < rear[k] && (Y(Q[k][rear[k]]) - Y(Q[k][rear[k] - 1])) * (q[pos] - q[Q[k][rear[k]]]) >= (Y(pos) - Y(Q[k][rear[k]])) * (q[Q[k][rear[k]]] - q[Q[k][rear[k] - 1]])) --rear[k];
			++rear[k];
			if(rear[k] >= (int)Q[k].size()) Q[k].push_back(pos);
			else Q[k][rear[k]] = pos;
		}
		for(j = 0;j < (int)id[i].size();j++){
			pos = id[i][j],k = x[pos];
			while(front[k] < rear[k] && Y(Q[k][front[k] + 1]) - Y(Q[k][front[k]]) <= 2 * a * i * (q[Q[k][front[k] + 1]] - q[Q[k][front[k]]])) ++front[k];
			if((x[pos] ^ 1) && front[k] > rear[k]) continue;
			if(x[pos] == 1 && front[k] > rear[k]) temp = 0;
			else temp = Q[k][front[k]];
			f[pos] = f[temp] + a * (p[pos] - q[temp]) * (p[pos] - q[temp]) + b * (p[pos] - q[temp]) + c;
			buc[q[pos]].push_back(pos);
			if(y[pos] == n) res = min(res,f[pos] + q[pos]);
		}
	}
	printf("%lld\n",res);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

最后总结一下斜率优化的基本模式：首先判断是否含有同时与当前点和决策点有关的项，然后化点斜式求横纵坐标和最优决策斜率，依据单调性讨论维护凸壳的方法。剩下的实现，包括数据结构、初始化、维度就因题而异了。

Thank you for reading！