[APIO 2010] 特别行动队

把长度为 n 的序列 x 划成一段段, 设某段元素之和为 x, 则该段战斗力为 ax^2 + bx + c. 求每段战斗力之和的最大值. (1 ≤ n ≤ 10^6, -5 ≤ a ≤ -1, |b|,|c| ≤ 10^7, 1 ≤ x[i] ≤ 100) 战斗力是关于 的多项式. 向斜率优化的方向靠拢.

设 为前缀和, 为前 个元素战斗力之和的最大值, 则

令 , 则我们要求 这条直线的最大纵截距, 且直线过某一数据点 .

由于要最大化 , 所以直线是从 轴正无穷向负无穷移动, 维护上凸壳.

随 递增, 随 递减, 所以可以用队列维护. 先从队首删掉零或多个点, 求得 , 再从队尾删掉零或多个点, 加入 .

大于二次就不能斜率优化了, 因为包含 项.

const int N = 1e6 + 1;

typedef long long ll;
int a, b, c, s[N], Q[N], * p = Q, * q = Q-1;
ll f[N];

inline ll cross(ll x1, ll y1, ll x2, ll y2)
{
	return x1*y2 - x2*y1;
}
inline ll x(int i)
{
	return s[i];
}
inline ll y(int i)
{
	return f[i] + 1LL*a*s[i]*s[i];
}
int main()
{
	int n;
	scanf("%d%d%d%d", &n, &a, &b, &c);
	rep (i, 1, n+1) scanf("%d", s+i), s[i] += s[i-1];
	*++q = 0;
	rep (i, 1, n+1)
	{
		ll k = 2LL*a*s[i] + b;
		while (q-p > 0 && cross(x(*(p+1))-x(*p), y(*(p+1))-y(*p), 1, k) <= 0) ++p;
		f[i] = y(*p) - k*x(*p) + 1LL*a*s[i]*s[i] + 1LL*b*s[i] + c;
		
		ll x0 = x(i), y0 = y(i);
		while (q-p > 0 && cross(x(*q)-x0, y(*q)-y0, x(*(q-1))-x0, y(*(q-1))-y0) <= 0) --q;
		*++q = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}