传送门

显然考虑 $dp$ ，发现从右往左和从左往右是一样的，所以只考虑一边就行

发现对于切的左右端点，选择的 $s0$ 一定要为左右端点的贝壳大小，不然这个端点不产生贡献还不如分开来单个贡献

所以设 $f[i]$ 表示当前把 $1$ 到 $i$ 的都切了，产生的最大贡献，设 $c[i]$ 表示位置 $i$ 及之前大小为 $s[i]$ 的柠檬个数，有转移：

$f[i]=f[j-1]+s[i](c[i]-c[j]+1)^2,j \in [1,i]$，并且要满足 $s[i]=s[j]$ ，发现是个斜率优化的式子，拆开来：

$f[i]=f[j-1]+s[i](c[i]^2-2c[i](c[j]-1)+(c[j]-1)^2)$，再拆，变成

$f[j-1]+s[i](c[j]-1)^2=2s[i]c[i](c[j]-1)+f[i]-s[i]c[i]^2$，因为转移都是在同一个大小之间转移，所以 $s[i]$ 可以看成常数

所以 $y=f[j-1]+s[i](c[j]-1)^2$，$k=2s[i]c[i]$，$x=c[j]-1$，$b=f[i]-s[i]c[i]^2$，对每种 $s$ 都维护一个凸包即可

显然对于同一个 $s$， $k,x$ 都单调递增，并且求 $max$ ，所以维护上凸包

插点时从右边插，更新 $f$ 时也切凸包右边，用 $vector$ 维护凸包即可

注意先加当前点再更新 $f$（$j \in [1,i]$）

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef long double ldb;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); } return x*f; } const int N=2e5+,M=2e4+; int n,s[N],c[N],cnt[M]; ll f[N]; struct Vec{//向量 ldb x,y; Vec (ll a=,ll b=) { x=a,y=b; } inline ldb operator * (const Vec &tmp) const { return x*tmp.y-y*tmp.x; } }; struct Poi{//凸包点 ll f; int cj,s; Poi (ll a=,int b=,int c=) { f=a,cj=b,s=c; } inline ll calc(int i) { return f+1ll*s*(c[i]-cj+)*(c[i]-cj+); } inline ll X() { return 1ll*s*(cj-); } inline ll Y() { return f+1ll*s*(cj-)*(cj-); } }; inline Vec operator - (Poi &A,Poi &B) { return Vec( A.X()-B.X() , A.Y()-B.Y() ); } vector st[M];//每种s维护凸包
int main()
{
n=read();
for(int i=;i<=n;i++) s[i]=read(),c[i]=++cnt[s[i]]; for(int i=;i<=n;i++) { Poi t(f[i-],c[i],s[i]); int len=st[s[i]].size()-; while( len> && (st[s[i]][len]-st[s[i]][len-])*(t-st[s[i]][len-])>= ) st[s[i]].pop_back(),len--;
st[s[i]].push_back(t); len++;//先插入
while( len> && st[s[i]][len].calc(i) <= st[s[i]][len-].calc(i) ) st[s[i]].pop_back(),len--;
f[i]=st[s[i]][len].calc(i);//再更新
}
printf("%lld\n",f[n]);
return ;
}