主要思路

首先发现两端并不会影响，所以可以直接做分段的线性 DP。正常思考暴力，发现每次都需要枚举颜色，非常麻烦。但是我们可以发现一个特别好的性质：每一次区间的颜色都取决于这个区间的最后一个元素，因为意识到选其他颜色时，我们大可把这个区间的右端点进行调整，使得下一个区间不会更劣。

了解到这个之后，DP 就是 \(\Theta(n^2)\) 的了，考虑进一步优化。对这个 DP 的式子进行展开：

\[ f_{j – 1} + a_i(pre_j – 1)^2 = (2a_i pre_i)(pre_j – 1) + f_i – a_i pre_i^2 \]

当然，这是已经做成直线式的 DP 式子了，设置变量 \(x = (pre_j – 1), k = (2a_i pre_i), b = f_i – a_i pre_i^2, y = f_{j – 1} + a_i(pre_j – 1)^2\)。从原式中发现平方项，且增长速度快于 \(y = x\)，故具有决策单调性，所以只需要单调栈即可。加入元素之前，我们需要找到上两个决策之间的决策边界，然后判断一下决策边界是否大于新的决策边界，如果是就弹掉（因为不会前者更优）。

代码

// BZ4709.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

typedef long long ll;

int n, ai[MAX_N], idx[MAX_N], cnt[MAX_N];
ll dp[MAX_N];
deque<int> stk[MAX_N];

ll calc(int x, ll y) { return dp[x - 1] + 1LL * ai[x] * y * y; }

int check(int x, int y)
{
    int l = 1, r = n, res = n + 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (calc(x, mid - idx[x] + 1) >= calc(y, mid - idx[y] + 1))
            r = mid - 1, res = mid;
        else
            l = mid + 1;
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &ai[i]), x = ai[i];
        idx[i] = ++cnt[ai[i]];
        while (stk[x].size() >= 2 && check(stk[x][stk[x].size() - 2], stk[x].back()) <= check(stk[x].back(), i))
            stk[x].pop_back();
        stk[x].push_back(i);
        while (stk[x].size() >= 2 && check(stk[x][stk[x].size() - 2], stk[x].back()) <= idx[i])
            stk[x].pop_back();
        dp[i] = calc(stk[x].back(), idx[i] - idx[stk[x].back()] + 1);
    }
    printf("%lld\n", dp[n]);
    return 0;
}