1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=35005;
int n,k,cur[maxn],pre[maxn],f[maxn][60];
struct SegmentTree{
#define ls (ro<<1)
#define rs (ro<<1|1)
struct tree{
int l,r,tag,v;
}e[maxn<<2];
inline void pushup(int ro){
e[ro].v=max(e[ls].v,e[rs].v);
}
inline void pushdown(int ro){
e[ls].tag+=e[ro].tag;e[rs].tag+=e[ro].tag;
e[ls].v+=e[ro].tag;e[rs].v+=e[ro].tag;
e[ro].tag=0;
}
void build(int ro,int l,int r){
e[ro].l=l,e[ro].r=r;
if(l==r)return;
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void rebuild(int tim,int ro){
int l=e[ro].l,r=e[ro].r;
e[ro].tag=0;
if(l==r){
e[ro].v=f[l][tim];return;
}
rebuild(tim,ls);rebuild(tim,rs);
pushup(ro);
}
void update(int ro,int x,int y){
int l=e[ro].l,r=e[ro].r;
if(l>=x and r<=y){
e[ro].v+=1;
e[ro].tag+=1;return;
}
pushdown(ro);
int mid=l+r>>1;
if(mid>=x)update(ls,x,y);
if(mid<y)update(rs,x,y);
pushup(ro);
}
int query(int ro,int x,int y){
int l=e[ro].l,r=e[ro].r;
if(l==x and r==y)return e[ro].v;
pushdown(ro);
int mid=l+r>>1;
if(mid<x)return query(rs,x,y);
else if(mid>=y)return query(ls,x,y);
else return max(query(ls,x,mid),query(rs,mid+1,y));
}
#undef ls
#undef rs
}T;
inline void work(){
n=read(),k=read();
for(int x,i=1;i<=n;i++)x=read(),pre[i]=cur[x],cur[x]=i;
T.build(1,0,n);
for(int i=1;i<=k;i++){
T.rebuild(i-1,1);
for(int x=1;x<=n;x++) T.update(1,pre[x],x-1),f[x][i]=T.query(1,0,x-1);
}
printf("%d",f[n][k]);
}
}
signed main(){
star::work();
return 0;
}
|
