记录编号	448897	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	K个串	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	4.756 s
提交时间	2017-09-13 15:51:59	内存使用	269.64 MiB

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
typedef long long ll;
using std::max;
const int MAXN = 200005;
std::map<int,int>last;
int a[MAXN],pre[MAXN],n,k,cnt;
 
 
template<typename _t>
inline _t read(){
    _t x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}
 
struct pa{
    ll mx;int pos;
    inline pa operator + (const ll &x)const{
        pa Ans;
        Ans.mx = mx + x;
        Ans.pos = pos;
        return Ans;
    }
    inline bool operator < (const pa & a)const{return mx<a.mx;}
};
 
void operator += (pa &x,ll k){x = x + k;}
 
struct data{
    int l,r,root; pa mx;
    inline bool operator < (const data & x)const{return mx < x.mx;}
};
 
std::priority_queue<data>Q;
 
struct node{int l,r;ll add;pa mx;}tree[MAXN*50];
int root[MAXN];
 
#define ls tree[o].l,tree[old].l,l,mid
#define rs tree[o].r,tree[old].r,mid+1,r
 
inline void Maintain(int o,int l,int r){
    if(l == r) return;
    tree[o].mx = max(tree[tree[o].l].mx,tree[tree[o].r].mx) + tree[o].add;
}
 
inline void build(int &o,int l,int r){
    o = ++ cnt;
    tree[o].mx = (pa){0,l};tree[o].add = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(tree[o].l,l,mid);
    build(tree[o].r,mid+1,r);
}
 
inline void Update(int &o,int old,int l,int r,int x,int y,ll val){
    if(x>y) return;
    o = ++ cnt; tree[o] = tree[old];
    if(x<=l&&r<=y) {tree[o].add += val; tree[o].mx += val; return;}
    register int mid = l + r >> 1;
    if(x<=mid) Update(ls,x,y,val);
    if(mid<y)  Update(rs,x,y,val); 
    Maintain(o,l,r);
}
 
inline pa Query(int o,int l,int r,int x,int y,ll add){
    if(x == l&&r == y) return tree[o].mx + add;
    register int mid = l + r >> 1;
    if(y<=mid) return Query(tree[o].l,l,mid,x,y,add+tree[o].add);
    else if(x>mid) return Query(tree[o].r,mid+1,r,x,y,add+tree[o].add);
    return max(Query(tree[o].l,l,mid,x,mid,add+tree[o].add),Query(tree[o].r,mid+1,r,mid+1,y,add+tree[o].add));
}
 
inline void work(int rt,int l,int r){
    if(l>r) return;
    data now;
    now.root = rt;
    now.mx = Query(rt,1,n,l,r,0);
    now.l = l; now.r = r;
    Q.push(now);
}
 
int main(){
    freopen("bzoj_4504.in","r",stdin);
    freopen("bzoj_4504.out","w",stdout);
    n = read<int>(); k = read<int>();
    for(int i = 1;i<=n;i++) {
        a[i] = read<int>();
        if(!last.count(a[i])) last[a[i]] = 0;
        pre[i] = last[a[i]],last[a[i]] = i;
    }
    build(root[0],1,n);
    for(int i = 1;i<=n;i++) Update(root[i],root[i-1],1,n,pre[i]+1,i,a[i]),work(root[i],1,i);
    k--;
    while(k --){
        data tmp = Q.top(); Q.pop();
        work(tmp.root,tmp.l,tmp.mx.pos-1);
        work(tmp.root,tmp.mx.pos+1,tmp.r);
    } printf("%lld\n",Q.top().mx.mx);
    return 0;
}