#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=450;
int n,i,j,a[N],b[N],k;
int l[M],cnt[M][N],p[M],c[N];
int dp[N];
struct FSI {
	template<typename T>
	FSI& operator >> (T &res) {
		res = 0; T f = 1; char ch = getchar();
		while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
		while (isdigit(ch)) {res = res * 10 + ch - '0'; ch = getchar();}
		res *= f;
		return *this;
	}
}scan;
int main()
{
	scan>>n;
	for (i=1;i<=n;i++) scan>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	k=unique(b+1,b+n+1)-b-1;
	for (i=1;i<=n;i++) a[i]=lower_bound(b+1,b+k+1,a[i])-b;
	for (i=1;i*i<=n;i++) l[i]=1;
	for (i=1;i<=n;i++)
	{
		for (j=1;j*j<=n;j++)
		{
			if (!cnt[j][a[i]])
			{
				p[j]++;
				while (l[j]<=i&&p[j]>j)
				{
					cnt[j][a[l[j]]]--;
					if (!cnt[j][a[l[j]]]) p[j]--;
					l[j]++;
				}
			}
			cnt[j][a[i]]++;
		}
		dp[i]=i;
		for (j=1;j*j<=i;j++) dp[i]=min(dp[i],dp[l[j]-1]+j*j);
	}
	printf("%d",dp[n]);
	return 0;
}

第一次，把小的放前面，内存应该更连续，反而TLE了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=450;
int n,i,j,a[N],b[N],k;
int l[M],cnt[N][M],p[M],c[N];
int dp[N];
struct FSI {
	template<typename T>
	FSI& operator >> (T &res) {
		res = 0; T f = 1; char ch = getchar();
		while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
		while (isdigit(ch)) {res = res * 10 + ch - '0'; ch = getchar();}
		res *= f;
		return *this;
	}
}scan;
int main()
{
	scan>>n;
	for (i=1;i<=n;i++) scan>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	k=unique(b+1,b+n+1)-b-1;
	for (i=1;i<=n;i++) a[i]=lower_bound(b+1,b+k+1,a[i])-b;
	for (i=1;i*i<=n;i++) l[i]=1;
	for (i=1;i<=n;i++)
	{
		for (j=1;j*j<=n;j++)
		{
			if (!cnt[a[i]][j])
			{
				p[j]++;
				while (l[j]<=i&&p[j]>j)
				{
					cnt[a[l[j]]][j]--;
					if (!cnt[a[l[j]]][j]) p[j]--;
					l[j]++;
				}
			}
			cnt[a[i]][j]++;
		}
		dp[i]=i;
		for (j=1;j*j<=i;j++) dp[i]=min(dp[i],dp[l[j]-1]+j*j);
	}
	printf("%d",dp[n]);
	return 0;
}

第二次随便换了个顺序，结果AC了，这样不应该常数更大吗