CXL.忘情
wqs二分水题，明显那个式子可以被化成 \((1+\sum x)^2\)，于是可以斜率优化，然后又明显随着段数越分越多函数是凹的，于是可以简单wqs二分。时间复杂度 \(O(n\log n)\)。
需要注意的是，因为二分上界是 \(10^{18}\)，所以得开 __int128。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
int n,m,s[100100],F[100100],q[100100],l,r;
ii f[100100];
inline void print(ii x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
ll sqr(int x){return 1ll*x*x;}
int che(ll ip){
// printf("%lld\n",ip);
l=r=0;
for(int i=1;i<=n;i++){
while(l<r&&f[q[l]]-f[q[l+1]]+sqr(s[q[l]])-sqr(s[q[l+1]])-2*(s[q[l]]-s[q[l+1]])>2ll*s[i]*(s[q[l]]-s[q[l+1]]))l++;
// printf("%d:%d\n",i,q[l]);
f[i]=f[q[l]]+sqr(s[i]-s[q[l]]+1)+ip,F[i]=F[q[l]]+1;
while(l<r&&(f[q[r-1]]-f[q[r]]+sqr(s[q[r-1]])-sqr(s[q[r]]))*(s[q[r]]-s[i])>(f[q[r]]-f[i]+sqr(s[q[r]])-sqr(s[i]))*(s[q[r-1]]-s[q[r]]))r--;
q[++r]=i;
}
// for(int i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
int L=F[n];
l=r=0;
for(int i=1;i<=n;i++){
while(l<r&&f[q[l]]-f[q[l+1]]+sqr(s[q[l]])-sqr(s[q[l+1]])-2*(s[q[l]]-s[q[l+1]])>=2ll*s[i]*(s[q[l]]-s[q[l+1]]))l++;
f[i]=f[q[l]]+sqr(s[i]-s[q[l]]+1)+ip,F[i]=F[q[l]]+1;
while(l<r&&(f[q[r-1]]-f[q[r]]+sqr(s[q[r-1]])-sqr(s[q[r]]))*(s[q[r]]-s[i])>=(f[q[r]]-f[i]+sqr(s[q[r]])-sqr(s[i]))*(s[q[r-1]]-s[q[r]]))r--;
q[++r]=i;
}
int R=F[n];
// printf("[%d,%d]\n",L,R);
if(L>m)return 1;
if(R<m)return -1;
print(f[n]-(ii)ip*m);
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
ll L=0,R=1e18,mid;
while(true){
int tp=che(mid=(L+R)>>1);
if(tp==-1)R=mid-1;
if(tp==1)L=mid+1;
if(!tp)break;
}
return 0;
}