P5504\

/*
1.能否二分答案?
2.可以倒着思考问题?
3.打一个小表
4.寻找结论(答案就那几种?)
5.是DP & 记忆化搜索吗?
6.是否有单调性?
7.注意取模(数字写没写错 , 是否取了模)
8.能否tarjan缩个点? (点双边双强)
9.离线?
10.用一下莫队(珂朵莉树)?
11.怎么都到这一条了(模拟退火)
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0;
array<int , 200100> col , dp , val , cnt;
vector<int> que[20100];
inline int X(int id)
{
	return val[id];
}
inline int Y(int id)
{
	return dp[id - 1] + col[id] * val[id] * val[id] - 2 * col[id] * val[id]; 
}
inline int calc(int a , int b)
{
	return dp[b - 1] + col[a] * (val[a] - val[b] + 1) * (val[a] - val[b] + 1);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for(int i = 1;i <= n;++ i)
	{
		cin >> col[i];
		val[i] = ++ cnt[col[i]];
	}
	for(int i = 1;i <= n;++ i)
	{
		while(que[col[i]].size() > 1 && __int128(Y(que[col[i]][que[col[i]].size() - 1]) - Y(que[col[i]][que[col[i]].size() - 2])) * (X(i) - X(que[col[i]][que[col[i]].size() - 2])) <= __int128(Y(i) - Y(que[col[i]][que[col[i]].size() - 2])) * (X(que[col[i]][que[col[i]].size() - 1]) - X(que[col[i]][que[col[i]].size() - 2]))) que[col[i]].pop_back();
		que[col[i]].push_back(i);
		while(que[col[i]].size() > 1 && calc(i , que[col[i]][que[col[i]].size() - 1]) <= calc(i, que[col[i]][que[col[i]].size() - 2])) que[col[i]].pop_back();
		int nxt = que[col[i]][que[col[i]].size() - 1];
		dp[i] = dp[nxt - 1] + col[i] * (val[i] - val[nxt] + 1) * (val[i] - val[nxt] + 1); 
	}
	cout << dp[n] << endl;
	return 0;
}

能不能不用$calc()$函数实现第二个$while$，我自己写的斜率判别不对