题解：
解法1：
单调栈优化
首先发现一个性质就是
如果当前从i转移比从j转移更加优秀
那么之后就不会从j转移
所以我们考虑利用这个性质
我们要维护一个队列保证前一个超过后一个的时间单调不减
怎么来维护呢
我们计算s[t-2]超过s[t-1]的时间t1，s[t-1]超过i的时间t2，如果t1<t2就说明了s[t-1]没有用了
另外再更新的时候我们算一下相邻两个哪个比较有用，要是前面哪个就弹栈
解法2：
f[i]=max(f[j−1]+a[j]×(s[i]−s[j]+1)^2)
我们先尝试一下一般的斜率优化，会发现是不行的
因为会出现s[i]^2和s[i]两项
我们转化一下这个式子
f[j−1]+(s[j]−1)2∗color=2∗s[i]∗color∗(s[j]−1)+f[i]−s[i]∗v[i]
把左边看成y，右边（s[j]-1）看成y，2*s[i]*color看成系数，后面的看成b
问题就变成了一条直线切割的b最大
显然凸包维护就可以了
代码：
#include <bits/stdc++.h> using namespace std; #define IL inline #define ll long long #define rint register int #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define me(x) memset(x,0,sizeof(x)) const int INF=1e9; const int N=2e5+10; int n; ll f[N]; vector<int> g[N]; int s[N],a[N],cnt[N]; IL ll calc(int x,int y) { return f[x-1]+1ll*a[x]*y*y; } IL int find(int x,int y) { int h=max(s[x],s[y]),t=n; while(h<t) { int mid=(h+t)/2; if (calc(x,mid-s[x]+1)>=calc(y,mid-s[y]+1)) t=mid; else h=mid+1; } return(h); } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); ios::sync_with_stdio(false); cin>>n; rep(i,1,n) { int x; cin>>x; a[i]=x; s[i]=++cnt[x]; int k1=g[x].size(); while (k1>=2&&find(g[x][k1-2],g[x][k1-1])<=find(g[x][k1-1],i)) g[x].pop_back(),k1--; g[x].push_back(i); k1++; while (k1>=2&&find(g[x][k1-2],g[x][k1-1])<=s[i]) g[x].pop_back(),k1--; f[i]=calc(g[x][k1-1],s[i]-s[g[x][k1-1]]+1); } cout<<f[n]; return 0; }