复习一下斜率优化：

令 $f_{i}$ 表示从 1 考虑到 $i$ 的最优结果.

得 $f_{i}=min${ $f_{j}+(sum_{i}-sum_{j}+i-j-1-L)^{2}$}

如果直接枚举，是 $O(n^{2})$ 的，太慢了!!!

考虑斜率优化:

令 $k<j$，考虑什么时候 $j$ 比 $k$ 优：

$fj​+(sumi​−sumj​+i−j−1−L)^{2}<fk​+(sumi​−sumk​+i−k−1−L)^{2}$

令 $a_{i}=sum_{i}+i$ ，$b_{i}=sum_{i}+i+1+L$ (为了简化计算）

得： $f_{j}+(a_{i}-b_{j})^{2}<f_{k}+(a_{i}-b_{k})^{2}$

化简一下，得：$\frac{f_{j}+b_{j}^{2}-(f_{k}+b_{k}^{2})}{b_{j}-b_{k}}<2\times a_{i}$

令 $g[x]=f_{x}+b_{x}^{2}$

上面式子为 $\frac{g_{j}-g_{k}}{b_{j}-b{k}}$,看上去是不是很熟悉 ？

这不就是一次函数斜率得形式嘛......

可以把 $j,k$ 都看作二维平面上的点 $(b_{j},g_{j})$ 与 $(b_{k},g_{k})$

那么， $j$ 的答案优于 $k$ 是在二者得斜率小于 $2\times a_{i}$ 的情况下成立的.

所以说，我们要求的 $j$ 就是编号最大的与前一个点的斜率小于 $2a_{i}$ 的值. 

手画一下，发现这道题中我们要维护的其实就是一个下凸包.

根据我们每一次的斜率 $2\times a_{i}$,不难发现这个东西是单调递增的，所以当我们找到答案 $tmp$ 时，$tmp$ 前的所有点就都变成无用点，直接弹掉即可.

而每一次新加入一个点，就顺便维护凸包的形状，将不合法的点从队尾弹出即可.     

#include
      
       #include
       
        using namespace std;const int maxn = 100000 + 123;long long s[maxn], f[maxn];int l, n, q[maxn];inline long long  re_x(int i){ return s[i]; }inline long long  re_y(int i){ return f[i] + (s[i] + l) * (s[i] + l); }inline double get_slope(int i,int j){return (double)(re_y(i) - re_y(j)) / (re_x(i) - re_x(j)); }int main(){    scanf("%d%d",&n,&l);    for(int i = 1;i <= n; ++i) scanf("%lld",&s[i]), s[i] += s[i-1];    for(int i = 1;i <= n; ++i) s[i] += i;    int head = 0, tail = 0;    for(int i = 1;i <= n; ++i)    {        while(head < tail && get_slope(q[head], q[head + 1]) < 2 * s[i] ) ++ head;        f[i] = f[q[head]] + (s[i] - s[q[head]] - 1 - l) * (s[i] - s[q[head]] - 1 - l);        while(tail > head && get_slope(q[tail], i) < get_slope(i, q[tail - 1])) --tail;        q[++tail] = i;    }    printf("%lld",f[n]);    return 0;}