考虑对于一个点，能转移来的只有一条单调下降的序列和一条单调上升的序列。
那么我们直接用单调栈维护这两个，同时发现转移的形式是跟斜率优化类似的，套用斜率优化即可，对于一个序列在同一个单调栈上维护 \(a_i\) 的单调和斜率的单调。
注意两条链使用斜率优化时的符号不一样。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll __int128
#define db double
using namespace std;
const int N=1e6+10;
int n,m,a[N],la[N],q1[N],q2[N],r1,r2;
ll f[N],ans;
int b[N],tot=0;
ll sqr(ll a){return a*a;}
void write(ll ans){
while(ans){
b[tot++]=ans%10;
ans/=10;
}
fd(i,tot-1,0)printf("%d",b[i]);
}
db calc(int x,int y){
return (db)(f[x]-f[y] + sqr(a[x]) - sqr(a[y])) / (db)(a[x]-a[y]) / 2;
}
int main(){
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,1,n)scanf("%d",&a[i]);
r1=r2=1;
q1[1]=q2[1]=1;
fo(i,2,n){
while(r1>1 && calc(q1[r1-1],q1[r1])>a[i])--r1;
while(r2>1 && calc(q2[r2-1],q2[r2])<a[i])--r2;
int t=q1[r1];
f[i]=f[t] + m + sqr(a[i] - a[t]);
t=q2[r2];
f[i]=max(f[i],f[t] + m + sqr(a[i] - a[t]));
ans=max(ans,f[i]);
while(r1 && a[q1[r1]]<=a[i])--r1;
while(r2 && a[q2[r2]]>=a[i])--r2;
while(r1>1 && calc(q1[r1-1],q1[r1])>=calc(q1[r1],i))--r1;
while(r2>1 && calc(q2[r2-1],q2[r2])<=calc(q2[r2],i))--r2;
q1[++r1]=q2[++r2]=i;
}
write(ans);
return 0;
}