题目链接

//BZOJ #4504
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
typedef pair<PII,int> PPI;
const int N=1e5+5,INF=LLONG_MAX/3;
int rt[N],tot=0;
struct node
{
	int l,r,tag;
	PII mx;
}T[N<<7];
map<int,int> mp;
priority_queue<PPI> q;
void build(int &p,int l,int r)
{
	T[p=++tot].mx=PII(0,r);
	if(l==r)return;
	int mid=(l+r)>>1;
	build(T[p].l,l,mid);
	build(T[p].r,mid+1,r);
	return;
}
void modify(int &o,int p,int l,int r,int x,int y,int v,int tg)
{
	if(!o)T[o=++tot]=T[p];
	if(x<=l&&r<=y)return T[o].mx.first+=v,T[o].tag+=v,void();
	int mid=(l+r)>>1,&ls=T[o].l,&rs=T[o].r;
	tg+=T[p].tag; 
	if(x<=mid)modify(ls=0,T[p].l,l,mid,x,y,v,tg);
	if(y>mid)modify(rs=0,T[p].r,mid+1,r,x,y,v,tg);
	T[o].mx=max(T[ls].mx,T[rs].mx);
	T[o].mx.first+=T[o].tag;
	return;
}
PII query(int p,int l,int r,int x,int y,int tg)
{
	if(x>r||y<l)return PII(-INF,-1);
	if(x<=l&&r<=y)return PII(T[p].mx.first+tg,T[p].mx.second);
	int mid=(l+r)>>1;
	PII resL=query(T[p].l,l,mid,x,y,tg+T[p].tag);
	PII resR=query(T[p].l,mid+1,r,x,y,tg+T[p].tag);
	return max(resL,resR);
}
signed main()
{
	int n,k;
	scanf("%lld %lld",&n,&k);
	build(rt[0],1,n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%lld",&x);
		modify(rt[i],rt[i-1],1,n,mp[x]+1,i,x,0);
		q.push(PPI(query(rt[i],1,n,1,i,0),i));
		mp[x]=i;
	}
	for(int i=1;i<k;i++)
	{
		int L=q.top().first.second,R=q.top().second;
		q.pop();
		modify(rt[R],rt[R],1,n,L,L,-INF,0);
		q.push(PPI(query(rt[R],1,n,1,R,0),R));
	}
	printf("%lld",q.top().first.first);
	return 0;
}