/*

思路

s是值等于a[i]的前缀和

转移方程$f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1))$

不难写出暴力方程(by wxyww)

//@baoli

memset(f,-0x3f,sizeof(f));

f[0]=0;

for(int i=1;i<=n;++i) {

	for(int j=1;j<=i;++j) {

		if(a[i]==a[j]) {

			f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1));

		}

	}

}

关于此题的单调性

特性1

每一段分出来的都一定是两端相同的，显然

特性2

他满足斜率单调，也就是要维护凸包

ll X(int i) {return 2LL*a[i]*s[i];}

ll Y(int i) {return f[i-1]+1LL*a[i]*s[i]*s[i]-2LL*a[i]*s[i];}

特性3

如果\(j<k\)且\(f_{j-1}+a{i}*(s{i}-s{j}+1)^2 > f{k-1}+a{i}*(s{i}-s{k}+1)^2\)

显然，f和s都是单增的

那么对于i以后的点都是j决策大于k决策

为何？显然(我只能这样说)，大概可以理解为\(s{i}-s{j}\)的变化量比\(s{i}-s{k}\)大0

总结思路，把他们用栈一起维护起来就是了？

错误

全程懵逼

代码

#include <cstdio>

#include <vector>

#define ll long long

using namespace std;

const int N=1e5+7;

int n,a[N],s[N],vis[N],top[N];

ll f[N];

vector<int> q[N];

ll X(int i) {return 2LL*a[i]*s[i];}

ll Y(int i) {return f[i-1]+1LL*a[i]*s[i]*s[i]-2LL*a[i]*s[i];}

long double calc(int j,int k) {return (Y(k)-Y(j))/(long double)(X(k)-X(j));}

ll dp(int i,int j) {return f[j-1]+(ll)a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1);}

int main() {

	scanf("%d",&n);

    for(int i=1;i<=n;++i) scanf("%d",&a[i]),s[i]=++vis[a[i]];

    for(int i=1;i<=n;++i) if(!q[a[i]].size()) q[a[i]].push_back(0);

    for(int i=1;i<=n;++i) {

        ll p=a[i];

        while(top[p]>1 && calc(q[p][top[p]],q[p][top[p]-1]) <= calc(q[p][top[p]],i))

            top[p]--,q[p].pop_back();

        top[p]++;q[p].push_back(i);

        while(top[p]>1 && calc(q[p][top[p]],q[p][top[p]-1]) <= s[i])

            top[p]--,q[p].pop_back();

        f[i]=dp(i,q[p][top[p]]);

    }

    printf("%lld\n", f[n]);

    return 0;

}