ITK24_DP1

Lưu ý bài này giải theo cấu trúc Segment Tree

Bộ ba đẹp

Một bộ ba số \((𝑥, 𝑦, 𝑧)\) được gọi là bộ ba đẹp nếu tồn tại một số bằng tổng hai số còn lại. Ví dụ, các
bộ ba (5,1,4), (0,1,1) hay (0,0,0) là các bộ ba đẹp, còn bộ (3,4,5) không phải là bộ ba đẹp.
Xét dãy số nguyên không âm \(a_1,a_2,..., a_n\) , bộ ba chỉ số \((𝑖, 𝑗, 𝑘)\) được gọi là bộ ba chỉ số BTRI của
dãy nếu thỏa mãn các điều kiện sau:

\(1) 1 ≤ 𝑖 < 𝑗 < 𝑘 ≤ 𝑛\);

\(2) (𝑎_𝑖, 𝑎_𝑗, 𝑎_𝑘)\) là bộ ba đẹp.

Yêu cầu: Cho dãy số nguyên không âm \(a_1,a_2,..., a_n\), hãy đếm số bộ ba chỉ số BTRI của dãy.

Input:

• Dòng đầu tiên chứa một số nguyên dương \(𝑛\);
• Dòng thứ hai chứa \(𝑛\) số nguyên không âm \(a_1,a_2,..., a_n\) \((𝑎_𝑖 \le 1000)\).

Output:

• Một số nguyên là số bộ BTRI của dãy \(a_1,a_2,..., a_n\).

Ví dụ:

Input:

4
1 2 3 4

Output:

2

• Có 25% số test của bài có \(n = 3\);
• Có 25% số test khác của bài có \(n \le 10^2\);
• Có 25% số test khác của bài có \(n \le 10^3\);
• Có 25% số test còn lại của bài có \(n \le 10^5\).

Lớp học nhảy

Một lớp học nhảy có \(𝑛\) học viên, học viên thứ \(𝑖\) có chiều cao là \(ℎ_𝑖 (𝑖 = 1,2, … , 𝑛)\). Trong một buổi
học, sau khi hướng dẫn cho tất cả các học viên, thầy giáo muốn chọn ra \(𝑘\) đôi nhảy, mỗi đôi gồm
hai học viên để trình diễn và rút kinh nghiệm. Với một đôi nhảy, chênh lệch chiều cao giữa hai
học viên càng nhỏ càng tốt, do đó, thầy giáo muốn lựa chọn ra \(𝑘\) đôi nhảy mà tổng các chênh lệch
chiều cao giữa hai học viên trong cùng một đôi của cả \(𝑘\) đôi là nhỏ nhất.

Yêu cầu: Cho \(𝑛\) số nguyên dương \(ℎ_1, ℎ_2, … , ℎ_𝑛\) là chiều cao của \(𝑛\) học viên và số nguyên dương
\(𝑘\), hãy chọn ra \(𝑘\) đôi nhảy mà tổng các chênh lệch chiều cao giữa hai học viên trong cùng một đôi
của cả \(𝑘\) đôi là nhỏ nhất.

Input:

• Dòng đầu chứa hai số nguyên dương \(𝑛, 𝑘 (𝑘 ≤ |𝑛/2|\), trong đó \(|𝑛/2|\) là số nguyên lớn nhất
  không vượt quá \(𝑛/2\));
• Tiếp theo là một dòng chứa \(𝑛\) số nguyên dương \(ℎ_1, ℎ_2, … , ℎ_𝑛 (ℎ_i \le 10^9)\)

Output:
một số là số tổng các chênh lệch chiều cao giữa hai
học viên trong cùng một đôi của cả \(𝑘\) đôi là nhỏ nhất

Ví dụ:

Input:

5 2
2 5 3 3 6

Output:

1

• Có 40% số lượng test ứng với 40% số điểm của bài thỏa mãn: \(𝑛 \le 10\);
• Có 30% số lượng test khác ứng với 30% số điểm của bài thỏa mãn: \(𝑛 ≤ 1000; 𝑘 = |𝑛/2|\);
• Có 30% số lượng test còn lại ứng với 30% số điểm của bài thỏa mãn: \(𝑛 ≤ 1000\).