记录编号	248767	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	K个串	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	13.004 s
提交时间	2016-04-11 13:24:43	内存使用	176.35 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=100010;
const int INF=23333333;
int hash[maxn],a[maxn],n,k;
int head[maxn],nxt[maxn],pre[maxn];
int rt[maxn],pos[maxn<<6];
int ch[maxn<<6][2],cnt;
long long lx[maxn<<6],tr[maxn<<6];
void Push_up(int x){
	int l=ch[x][0],r=ch[x][1];
	tr[x]=tr[l]+tr[r];
	if(lx[l]>tr[l]+lx[r]){
		lx[x]=lx[l];
		pos[x]=pos[l];
	}
	else{
		lx[x]=tr[l]+lx[r];
		pos[x]=pos[r];
	}
}
void Build(int &rt,int l,int r){
	rt=++cnt;
	if(l==r){
		pos[rt]=l;
		if(!pre[l]){
			tr[rt]=hash[a[l]];
			lx[rt]=hash[a[l]];
		}
		return;
	}
	int mid=(l+r)>>1;
	Build(ch[rt][0],l,mid);
	Build(ch[rt][1],mid+1,r);
	Push_up(rt);
}

void Update(int pr,int &rt,int l,int r,int g,int d){
	rt=++cnt;
	tr[rt]=tr[pr]+d;
	if(l==r){
		pos[rt]=g;    
		lx[rt]=tr[rt];
		return;
	}
	ch[rt][0]=ch[pr][0];
	ch[rt][1]=ch[pr][1];
	int mid=(l+r)>>1;
	if(g<=mid)Update(ch[pr][0],ch[rt][0],l,mid,g,d);
	else Update(ch[pr][1],ch[rt][1],mid+1,r,g,d);
	Push_up(rt);
}
struct data{int x;long long y;};
data Query(int t,int l,int r,int x,int y)
{
	if(l==x && r==y) return (data){pos[t],lx[t]};
	int mid=(l+r)>>1;
	if(y<=mid) return Query(ch[t][0],l,mid,x,y);
	else if(x>mid){
		data tmp=Query(ch[t][1],mid+1,r,x,y);
		return (data){tmp.x,tmp.y+tr[ch[t][0]]};
	}
	else{
		data tmp1=Query(ch[t][0],l,mid,x,mid);
		data tmp2=Query(ch[t][1],mid+1,r,mid+1,y);
		if(tmp1.y>tmp2.y+tr[ch[t][0]]) return tmp1;
		else return (data){tmp2.x,tmp2.y+tr[ch[t][0]]};
	}
}

struct node{int i,l,r,x; long long y;};
bool operator<(const node& a1,const node& a2)
{return a1.y<a2.y;}
priority_queue<node> q;

int main(){
	freopen("bzoj_4504.in","r",stdin);
	freopen("bzoj_4504.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		hash[i]=a[i];
	sort(hash+1,hash+n+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(hash+1,hash+n+1,a[i])-hash;
	for(int i=1;i<=n;i++){
		pre[i]=head[a[i]];
		nxt[head[a[i]]]=i;
		head[a[i]]=i;
	}
	Build(rt[1],1,n);
	for(int i=1;i<n;i++){
		Update(rt[i],rt[i+1],1,n,i+1,-hash[a[i]]);
		if(nxt[i])Update(rt[i+1],rt[i+1],1,n,nxt[i],hash[a[i]]);
	}
	for(int i=1;i<=n;i++){
		data tmp=Query(rt[i],1,n,i,n);
		q.push((node){i,i,n,tmp.x,tmp.y});
	}
	long long ans;
	for(int i=1;i<=k;i++){
		node t=q.top(); q.pop(); ans=t.y;
		if(t.l!=t.x){
			data tmp=Query(rt[t.i],1,n,t.l,t.x-1);
			q.push((node){t.i,t.l,t.x-1,tmp.x,tmp.y});
		}
		if(t.r!=t.x){
			data tmp=Query(rt[t.i],1,n,t.x+1,t.r);
			q.push((node){t.i,t.x+1,t.r,tmp.x,tmp.y});
		}
	}
	printf("%lld\n",ans);
	return 0;
}