记录编号	453506	评测结果	AAAAAAAAAA
题目名称	[USACO Mar09]餐厅清扫	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2017-09-21 16:56:06	内存使用	0.55 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=40000+10;
int n,m,tot,js,l,r;
int val[M],f[M],pre[M],nxt[M],col[M],pos[M],num[M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int DK(){
	freopen("cleanup.in","r",stdin);
	freopen("cleanup.out","w",stdout);
	memset(nxt,0x3f,sizeof(nxt));
	n=read();m=read();int xx;
	for(int i=1;i<=n;++i){
		xx=read();
		if(xx==val[tot]) continue;
		val[++tot]=xx;
	}
	for(int i=1;i<=tot;++i){
		int id=col[val[i]];
		pre[i]=id;nxt[id]=i;
		col[val[i]]=i;
	}nxt[0]=0;num[1]=1;
	for(int i=2;i<=tot;++i) {num[i]=num[i-1];if(!pre[i]) num[i]+=1;}
	for(int i=1;i<=tot;++i) f[i]=i;
	pos[1]=1;
	for(int i=2;i<=tot;++i){
		int lim=sqrt(f[i-1]+1);
		int id=pre[i];
		for(int j=1;j<=lim;++j){
			if(num[i]==j) {pos[j]=1;break;}
			if(id<pos[j]){
				for(int k=pos[j];k<=i;++k)
					if(nxt[k]>i) {pos[j]=k+1;break;}
			}else{
				if(pos[j]) continue;
				int k=pos[j-1]-1;
				for(;k>=1;--k) if(nxt[k]>i) {pos[j]=k;break;}
				--k;
				while(nxt[k]<=i) --k;
				pos[j]=k+1;
			}
		}
		for(int j=1;j<=lim;++j){
			if(!pos[j]) break;
			f[i]=min(f[i],f[pos[j]-1]+j*j);
		}
	}printf("%d\n",f[tot]);
	return 0;
}
int dk=DK();
int main(){;}