[mathjax]

### Brief description:

略。）

### Analysis:

首先写好暴力。

$$ f_i = \min_{0 <= j < i}{ f_j + (i-j+s_i-s_{j-1}-L)^2 | j < i} $$

观察，微调，分离常数。

REP_1(i, n) s[i] += i; ++L;

$$ \begin{aligned} f_i &= \min_{0 \leq j < i}{ f_j + ((s_i-L)-s_j)^2 } \ &= \min_{0 \leq j < i}{ -2(s_i-L)s_j + (f_j+s_j^2) } + (s_i-L)^2 \end{aligned} $$

写成斜率优化的标准形式，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]); }