10 
2
	3
2
2
	3
	3
1
1
	3
2

考虑这样一组数据，我们考虑颜色 3 的决策单调性（每个位置前 tab 了一下，方便看），网上都说同一颜色，具有决策单调性。可事实是什么呢？

我们发现 2 5 6 9 这三个颜色为 3 的最优决策点为 2 5 5 2，明显假了。。。

以下是查找每个 i 最优决策点（改自题解，方便大家验证。。。）

有没有大佬解释一下呢。。（

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int _ = 100000 + 10;
const int __ = 10000 + 10;
int n, tot[__];
ll s[_], c[_], f[_];
vector<int> stk[__];

inline ll X(int i) { return c[i]; }
inline ll Y(int i) { return f[i - 1] + s[i] * c[i] * c[i] - 2 * s[i] * c[i]; }
inline double slope(int i, int j) { return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j)); }
inline ll calc(int i, int j) { return f[j - 1] + s[i] * (c[i] - c[j] + 1) * (c[i] - c[j] + 1); }

#define t1 stk[t][stk[t].size() - 1]
#define t2 stk[t][stk[t].size() - 2]

int main() {
	freopen("in.in","r",stdin); 
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		c[i] = ++tot[s[i]];
	}
	for (int i = 1; i <= n; ++i) {
		int t = s[i];
		while (stk[t].size() >= 2 && slope(t2, i) >= slope(t2, t1)) stk[t].pop_back();
		stk[t].push_back(i);
		while (stk[t].size() >= 2 && calc(i, t1) <= calc(i, t2)) stk[t].pop_back();
		int j = stk[t][stk[t].size() - 1];
		printf("%d : ", i);
		for(int k = 1; k <= i; ++ k) {
			if(s[k] == s[i] && calc(i, k) == calc(i, j)) printf("%d ", k);
		} puts("");
		f[i] = calc(i, stk[t][stk[t].size() - 1]);
	}
	for(int i =1;i<=n;++i) cout << f[i] << ' ';
	return 0;
}