记录编号	371260	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	K个串	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	7.184 s
提交时间	2017-02-15 20:12:00	内存使用	256.87 MiB

#include <cstdio>
#include <map>
#include <queue>
using namespace std;
#define ll long long 
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-48,ch=getchar();
	return x*f;
}
const int maxn=101000;
map<int,int>mp;
int n,k,root[maxn];
struct Node{
	int rt,l,r,k;ll val;
	Node(int a,int b,int c,int d,ll e){
		rt=a,l=b,r=c,k=d,val=e;
	}
	bool operator < (const Node &x)const{return val<x.val;}
};
struct Tr{
	ll k,val;
	bool operator < (const Tr &x)const{return val<x.val;};
}tr[maxn*70];
int lc[maxn*70],rc[maxn*70],cnt;
ll sum[maxn*70],mx[maxn*70];
priority_queue<Node>q;
void insert(int l,int r,int pr,int &rt,int s,int t,ll x){
	sum[rt=++cnt]=sum[pr];
	lc[rt]=lc[pr],rc[rt]=rc[pr];
	if(s<=l&&t>=r){
		sum[rt]+=x;
		tr[rt].k=tr[pr].k;
		tr[rt].val=tr[pr].val+x;
		return;
	}int mid=(l+r)/2;
	if(s<=mid)insert(l,mid,lc[pr],lc[rt],s,t,x);
	if(t>mid)insert(mid+1,r,rc[pr],rc[rt],s,t,x);
	tr[rt]=(tr[lc[rt]]<tr[rc[rt]])?tr[rc[rt]]:tr[lc[rt]];
	tr[rt].val+=sum[rt];
}
Tr query(int rt,int l,int r,int s,int t){
	if(s<=l&&t>=r) return tr[rt];
	int mid=(l+r)/2;Tr ans;
	if(t<=mid) ans=query(lc[rt],l,mid,s,t);
	else if(s>mid) ans=query(rc[rt],mid+1,r,s,t);
	else{
		Tr a=query(lc[rt],l,mid,s,t);
		Tr b=query(rc[rt],mid+1,r,s,t);
		ans=(a<b)?b:a;
	}ans.val+=sum[rt];
	return ans;
}
void Build(int &rt,int l,int r){
	tr[rt=++cnt].k=l;
	if(l==r)return;int mid=(l+r)/2;
	Build(lc[rt],l,mid);Build(rc[rt],mid+1,r);
}
int main(){
	freopen("bzoj_4504.in","r",stdin);freopen("bzoj_4504.out","w",stdout);
	n=read(),k=read();
	Build(root[0],1,n);
	for(int i=1;i<=n;i++){
		int x=read(),pre=mp[x];mp[x]=i;
		insert(1,n,root[i-1],root[i],pre+1,i,x);
		Tr ans=query(root[i],1,n,1,i);
		q.push(Node(root[i],1,i,ans.k,ans.val));
	}
	ll ans=0;
	for(int i=1;i<=k;i++){
		Node x=q.top();q.pop();
		ans=x.val;
		if(x.l<x.k){
			Tr next=query(x.rt,1,n,x.l,x.k-1);
			q.push(Node(x.rt,x.l,x.k-1,next.k,next.val));
		}
		if(x.k<x.r){
			Tr next=query(x.rt,1,n,x.k+1,x.r);
			q.push(Node(x.rt,x.k+1,x.r,next.k,next.val));
		}
	}
	printf("%lld\n",ans);	
	fclose(stdin);fclose(stdout);
	return 0;
}