【题解】

首先dp方程很好列出，$f_{i} = min(f_{j} + (i-j-1 + s[i] - s[j] - L)^{2})$，很明显这是$O(n^2)$的，下面我们尝试优化它。

首先我们令$g_{i} = s_{i}+i, C=1+L$

那么$f_{i} = min(f_{j} + (g_{i}-g_{j}-C)^{2})$

1. 我们证明状态影响的持续性

假设现在有两个决策点可以转移,$f_{j}, f_{k}$，假设$j<k$，且决策$k$比$j$好

$f_{j} + (g_{i}-g_{j}-C)^{2} >= f_{k} +(g_{i} - g_{k} -C)^{2}$

那么对于$i$后的状态$T$，$f_{t} = f_{i}+V$; 

只要证明 

$f_{j} + (g_{t}-g_{j}-C)^{2} >= f_{k} +(g_{t} - g_{k} -C)^{2}$

$f_{j} + (g_{t}-g_{j}-C+V)^{2} >= f_{k} +(g_{t} - g_{k} -C+V)^{2}$

$f_{j} + (g_{i}-g_{j}-C)^{2} + V^{2} + 2V(g_{i} - g_{j} - C) >= f_{k} +(g_{t} - g_{k} -C)^{2} + 2V(g_{i} - g_{k} - C)$

那么很明显推出就是要证明：

$g_{i} - g_{j} -C$ >= $g_{i}-g_{k}-C$

那么$g_{j} <= g_{k}$，显然满足要求，所以状态有持续影响。

2. 求斜率方程

$f_{j} + (g_{i}-g_{j}-C)^{2} >= f_{k} +(g_{i} - g_{k} -C)^{2}$

$f_{j} + g_{i}^{2} + (g_{j}+C)^{2} - 2g_{i}(g_{j}+C) >= f_{k} + g_{i}^{2} + (g_{k}+C)^{2} - 2g_{i}(g_{k}+C)$

$f_{j}-f_{k} + (g_{j}+C)^2 - (g_{k}+C)^2 >= 2g_{i}(g_{j}-g_{k})$

$\frac{(f_{j}+(g_{j}+C)^2) - (f_{k} + (g_{k}+C)^2)}{2g_{j} - 2g_{k}} <= g_{i}$

是不是觉得特别眼熟？没错！就是斜率！

令$s_{i} = f_{i}+(g_{i}+C)^2, t_{i} = 2g_{i}$，那么$\frac{s_{k}-s_{j}}{t_{k}-t_{j}} <= g_{i}$

斜率小于等于一个定值？

再清晰一点，设$X(i, j)$表示i到j的斜率，那么$X(k, j) <= g_{i}$

也就是说，如果$X(k, j) <= g_{i}(j<k)$，那么说明k比j优。

那么这说明了什么呢？我们就可以用一个队列维护了！

3. 规定队列维护的规则

类似于维护一个凸壳作为决策，那么我们就要规定队列如何维护了

每次取出队首作为决策

A. 队首维护规则

假设$x, y(x<y)$为队首元素，若$X(y, x) <= g_{i}$，那么说明y比x优秀，把x扔掉。否则不需要维护

B. 队尾维护规则

维护一个斜率单调上升的队列，那么每次从队尾删去元素即可。

注意要点：由于$f_{i}$是单调上升的！！！

# include <stdio.h>
using namespace std;

int n;
long long C, s[50010], g[50010], f[50010], q[200010], head, tail;


inline double X(int i, int j) {
	return (f[i] - f[j] + (g[i]+C)*(g[i]+C) - (g[j]+C)*(g[j]+C))/(2.0*(g[i] - g[j]));
}

int main() {
	scanf("%d%lld", &n, &C); ++C;
	for (int i=1, x; i<=n; ++i) {
		scanf("%d", &x);
		s[i] = s[i-1] + x;
		g[i] = s[i] + i;
	}
	head=1, tail=0;
	q[++tail]=0;	
	for (int i=1; i<=n; ++i) {
		while(head<tail && X(q[head], q[head+1]) <= g[i]) ++head;
		f[i] = f[q[head]] + (g[i] - g[q[head]] - C)*(g[i] - g[q[head]] - C);
		while(head<tail && X(q[tail-1], q[tail]) > X(q[tail], i)) tail--;
		q[++tail] = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}