Cặp Trùng Trong Đoạn · canuc80k4110

Cho dãy $a_{1}, a_{2}, \dots, a_{N}$ . Với một đoạn $[l, r]$ , chi phí của đoạn là số cặp chỉ số $(i, j)$ thỏa $l \leq i < j \leq r$ và $a_{i} = a_{j}$ . Mỗi cặp chỉ được đếm một lần.

Hãy chia dãy thành đúng $K$ đoạn liên tiếp không rỗng sao cho tổng chi phí của các đoạn nhỏ nhất.

Input

Dòng đầu gồm $N$ $K$ .
Dòng thứ hai gồm $a_{1}, a_{2}, \dots, a_{N}$ .

Output

In tổng chi phí nhỏ nhất.

Constraints

$2 \leq N \leq 1 0^{5}$ .
$2 \leq K \leq min (N, 20)$ .
$1 \leq a_{i} \leq N$ .
Kết quả dùng số nguyên $64$ bit.

Scoring

Subtask $1$ ( $50%$ ): $N \leq 70$ .
Subtask $2$ ( $50%$ ): không có ràng buộc thêm.

Example

Test 1

Input

7 3
1 1 3 3 3 2 1

Output

Giải thích: Chia dãy thành ba đoạn mang các giá trị [1], $[1, 3, 3]$ và $[3, 2, 1]$ . Chỉ đoạn giữa có một cặp phần tử bằng nhau, là cặp $3$ , nên tổng chi phí bằng $1$ .

Ý tưởng: Nếu một giá trị xuất hiện f lần trong đoạn, nó đóng góp f(f-1)/2. Duy trì cửa sổ [L,R], bảng tần suất và cost: khi thêm giá trị x, cộng số lần x hiện có rồi tăng tần suất; khi xóa, giảm tần suất trước rồi trừ tần suất mới.
Ý tưởng: Đặt dp[g][r] là chi phí nhỏ nhất cho r phần tử đầu với g đoạn. Đoạn cuối [p+1,r] cho recurrence min(dp[g-1][p]+cost(p+1,r)). Hàm số cặp bằng nhau là Monge (xét riêng từng giá trị), nên điểm chia tối ưu không giảm theo r; tính mỗi hàng bằng Divide and Conquer optimization và lấy cost qua cửa sổ động.
Ý tưởng: Các cập nhật thêm/xóa bảo toàn đúng số cặp; recurrence xét mọi đoạn cuối; tính Monge bảo đảm D&C không bỏ nghiệm. Độ phức tạp O(KN log N), bộ nhớ O(N).