柠檬
Flute很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 (n) ((1≤n≤100000)) 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 (1..n) 。每只贝壳的大小不一定相同，贝壳 (i) 的大小为 (s_i(1≤s_i≤10000)) 。 变柠檬的魔法要求Flute每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 (s_0)。如果这一小段贝壳中大小为 (s_0) 的贝壳有 (t) 只，那么魔法可以把这一小段贝壳变成 (s_0t^2) 只柠檬。Flute可以取任意多次贝壳，直到树枝上的贝壳被全部取完。各个小段中，Flute选择的贝壳大小 (s_0) 可以不同。而最终 Flute得到的柠檬数，就是所有小段柠檬数的总和。 Flute想知道，它最多能用这一串贝壳变出多少柠檬。请你帮忙解决这个问题。
题解
https://www.luogu.com.cn/blog/pks-LOVING/solution-p5504
对于一个(i)，设其最优决策点为(o_i)，那么一定有(color[i]=color[o_i])。
那么转移方程就很容易列出来：
观察这个式子，会发现一个性质，因为转移只在相同颜色间转移，所以对于后面的(color_icdot (sum_i-sum_j+1)^2)是随着(i)的变化而单增的，也就是说对于一个(j_1<j_2)，一开始时满足(j_1)更优，那么随着(i)增大(j_2)就永远不会比(j_1)更优，因为二次函数的增长对于更优的(j_1)只会增长得更快（类似于输在起跑线上233）。
所以发现是具有决策单调性的，即同一段区间的、同一种颜色的决策点会出现不增的局面。
那么一个自然的想法使用单调栈维护，发现第二个元素比第一个元素优的时候(pop)掉即可。但是问题在于当前点的最终决策点可能会更靠前，比如(j_1<j_2<j_3)但(val(j_1)>val(j_3)>val(j_2))，就应该从(j_1)转移。
但事实上，根据大趋势而言，出现上述那种情况当且仅当一段时间内(j_2)比(j_1)更优（否则当时就不会入栈），之后(j_1)开始比(j_2)优（导致出现了现在的(val(j_1)>val(j_2))）。所以我们可以二分出一个确定的时间（此处时间的流淌用新的(color_i)个数的增多刻画）优劣关系发生变化，而如果这个时间在(leq sum_i) 之前，那么就要(pop)掉(j_2)，因为没用了。
所以，每次加入元素的时候都要判断当前栈中(top-1)超过(top) 的元素的时间是否小于等于(top)超过要添加进来的(x)的时间，如果是就要把(top)给(pop)掉，因为在(top)超过(x)之前(top)就死了。
CO int N=1e5+10;
int bas[N],buc[N],s[N];
int64 dp[N];
vector<int> stk[N];
#define o(a,b) stk[a][b]
#define sz(a) stk[a].size()
#define sp(a) stk[a].size()-1
#define sq(a) stk[a].size()-2
IN int64 calc(int p,int t){
return dp[p-1]+(int64)bas[p]*t*t;
}
int chk(int x,int y){
int l=max(s[x],s[y]),r=N;
while(l<r){
int mid=(l+r)>>1;
if(calc(x,mid-s[x]+1)>=calc(y,mid-s[y]+1)) r=mid;
else l=mid+1;
}
return r;
}
int main(){
int n=read<int>();
for(int i=1;i<=n;++i) s[i]=++buc[read(bas[i])];
for(int i=1;i<=n;++i){
int t=bas[i];
while(sz(t)>=2 and chk(o(t,sq(t)),o(t,sp(t)))<=chk(o(t,sp(t)),i))
stk[t].pop_back();
stk[t].push_back(i);
while(sz(t)>=2 and chk(o(t,sq(t)),o(t,sp(t)))<=s[i])
stk[t].pop_back();
dp[i]=calc(o(t,sp(t)),s[i]-s[o(t,sp(t))]+1);
}
printf("%lld
",dp[n]);
return 0;
}