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
| #include<bits/stdc++.h>
#define REG register
#define MAXN 100005
#define LL long long
using namespace std;
inline int read(){
REG int x(0);
REG char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
inline Min(int a,int b){return a<b?a:b;}
int n,k;
int a[MAXN];
int t[MAXN];
int nowl=1,nowr;LL ans;
inline void LA(){--nowl,ans+=t[a[nowl]],++t[a[nowl]];}
inline void LD(){--t[a[nowl]],ans-=t[a[nowl]],++nowl;}
inline void RA(){++nowr,ans+=t[a[nowr]],++t[a[nowr]];}
inline void RD(){--t[a[nowr]],ans-=t[a[nowr]],--nowr;}
inline LL Ask(int L,int R){
while(nowl<L) LD();
while(nowl>L) LA();
while(nowr>R) RD();
while(nowr<R) RA();
return ans;
}
LL now[MAXN],lst[MAXN];
void Solve(int l,int r,int L,int R){
int mid=(l+r)>>1,p=mid;
for(int i=L;i<=Min(R,mid-1);++i)
if(Ask(i+1,mid)+lst[i]<=now[mid]) now[mid]=Ask(i+1,mid)+lst[i],p=i;
if(mid>l) Solve(l,mid-1,L,p);
if(mid<r) Solve(mid+1,r,p,R);
}
void Work(){
n=read(),k=read();
for(REG int i=1;i<=n;++i) a[i]=read(),now[i]=lst[i]=1ll*1e17;
for(REG int i=1;i<=k;++i){
Solve(1,n,0,n-1);
for(REG int j=1;j<=n;++j) lst[j]=now[j];
}
}
int main(){
Work();
printf("%lld\n",now[n]);
}
|
