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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long int64;
const int MAXN = 50010;
const int INF = 0x3f3f3f3f;
#include <cctype>
#include <cstdio>
inline int read() {
int X = 0, w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) {
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
int a[MAXN];
int last[MAXN];
int pre[MAXN];
int dp[MAXN][52];
namespace segtree {
int maxv[MAXN << 2], lazy[MAXN << 2];
void pushup(int rt) { maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]); }
void pushdown(int rt) {
if (lazy[rt] != 0) {
maxv[rt << 1] += lazy[rt];
maxv[rt << 1 | 1] += lazy[rt];
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
}
void build(int k, int l, int r, int rt) {
lazy[rt] = 0;
if (l == r) {
maxv[rt] = dp[l - 1][k];
return;
}
int mid = (l + r) >> 1;
build(k, l, mid, rt << 1);
build(k, mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int L, int R, int val, int l, int r, int rt) {
if (L <= l && r <= R) {
lazy[rt] += val;
maxv[rt] += val;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (L <= mid) update(L, R, val, l, mid, rt << 1);
if (R > mid) update(L, R, val, mid + 1, r, rt << 1 | 1);
pushup(rt);
}
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return maxv[rt];
}
pushdown(rt);
int mid = (l + r) >> 1;
int ans = 0;
if (L <= mid) ans = max(ans, query(L, R, l, mid, rt << 1));
if (R > mid) ans = max(ans, query(L, R, mid + 1, r, rt << 1 | 1));
return ans;
}
};
int main() {
int n = read();
int k = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
pre[i] = last[a[i]];
last[a[i]] = i;
}
for (int j = 1; j <= k; j++) {
segtree::build(j - 1, 1, n, 1);
for (int i = 1; i <= n; i++) {
segtree::update(pre[i] + 1, i, 1, 1, n, 1);
dp[i][j] = segtree::query(1, i, 1, n, 1);
}
}
cout << dp[n][k] << endl;
}
|
