summarization

有一个长度为 \(n\) 的序列 \(p\)，将其中若干个数标记。对于序列中的每一个位置 \(i\)，其贡献为其左边与右边离它最近的被标记的数的数值的和。求出最大的贡献总和。（\(1\le n\le2\times10^6\)）

solution

首先显然，\(p_1, p_n\) 一定要标记。然后考虑分别求相邻的标记数之间的贡献。

设 \(i,j\) 为相邻的两个标记数的位置。对于 \([i,j]\) 区间：\((i,j)\) 区间的贡献为 \((j-i-1)\times(p_i+p_j)\)，\(i\) 位置右边的贡献为 \(p_j\)，\(j\) 位置左边的贡献为 \(p_i\)，所以总和为 \((j-i)\times(p_i+p_j)\)。

发现 \((j-i)\times(p_i+p_j)\) 是梯形面积公式的一半，所以如果我们将每一个 \((i,p_i)\) 放入坐标系，那么贡献总和则等于如图阴影部分的面积的两倍：（红色的点为标记数所代表的点）

那么问题就变为选取若干个点，使其围成的梯形面积最大，显然选取上凸壳中的点即可。

时间复杂度 \(\mathcal{O}(n)\)

code

CI N = 2e6; ll n, p[N + 5], top = 0; struct node {ll x; ll y;} sk[N + 5];
ll cross (node a, node b, node c) {return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);}
int main () {
	RI i, j; for (Read (n), i = 1; i <= n; ++ i) Read (p[i]);
	for (i = 1; i <= n; ++ i) {
		node now = {i, p[i]}; W (top >= 2 && cross (sk[top - 1], sk[top], now) >= 0) -- top; sk[++ top] = now;
	} ll ans = 0; for (i = 1; i < top; ++ i) ans += (sk[i].y + sk[i + 1].y) * (sk[i + 1].x - sk[i].x);
	printf ("%lld\n", ans);
	return 0; 
}