[mathjax]
Brief description:
略。）
Analysis:
首先写好暴力。
观察，微调，分离常数。
REP_1(i, n) s[i] += i; ++L;
写成斜率优化的标准形式，b = kx + y
这里有：
- $k = -2(s_i-L)$
- $x = s_j $
- $y = f_j + x^2 $
这里 $x$ 和 $k$ 均单调（因为 $s_i$ 单调），单调队列即可。
//}/* .................................................................................................................................. */
const int N = int(5e4) + 9;
LL f[N], s[N]; int q[N], cz, op;
int n, L;
#define k (-2*(s[i]-L))
#define x(i) (s[i])
#define y(i) (f[i]+sqr(x(i)))
#define eval(i) (k*x(i)+y(i))
LL det(LL x1, LL y1, LL x2, LL y2){
return x1*y2 - x2*y1;
}
int dett(int p0, int p1, int p2){
LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));
return t < 0 ? -1 : t > 0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
RD(n, L); REP_1(i, n) s[i] = s[i-1] + RD();
REP_1(i, n) s[i] += i; ++L;
cz = 0, op = 0; q[cz] = 0; REP_1(i, n){
while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz;
f[i] = eval(q[cz]) + sqr(s[i]-L);
while (cz < op && dett(q[op-1], q[op], i) <= 0) --op;
q[++op] = i;
}
OT(f[n]);
}
