参考：http://hzwer.com/3917.html
好神啊
注意到如果分成n段，那么答案为n，所以每一段最大值为( sqrt{n} )
先把相邻并且值相等的弃掉
设f[i]为到i的最小答案，b[j]表示的是从b[j]+1开始到i共有j个不同的数字，p[a[i]]表示a[i]上次出现的位置，c[j]表示b[j]+1到i的不同数字个数
转移是f[i]=min(f[b[j]]+j*j)
b[i]的更改是每次i++时，先更新c，即如果p[a[i]]<=b[j]则c[j]++；
如果c[j]++了，那么就要从b[i]+1开始找一个只在b[j]+1到i出现一次的，删到它为止
时间复杂度为( O(nsqrt{n}) )
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=40005,S=205;
int n,m,a[N],f[N],b[S],c[S],p[N],tot;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
int main()
{
n=read(),m=read();
for(int i=0;i<=n;i++)
f[i]=1e9,p[i]=-1;
for(int i=1;i<=n;i++)
{
int x=read();
if(x!=a[tot])
a[++tot]=x;
}
n=tot,m=sqrt(n);
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
if(p[a[i]]<=b[j])
c[j]++;
p[a[i]]=i;
for(int j=1;j<=m;j++)
if(c[j]>j)
{
int now=b[j]+1;
while(p[a[now]]>now)
now++;
b[j]=now,c[j]--;
}
for(int j=1;j<=m;j++)
f[i]=min(f[i],f[b[j]]+j*j);
}
printf("%d
",f[n]);
return 0;
}