Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Người dân thành phố SQRT đang chuẩn bị đón Tết Ất Tỵ 2025.

Năm nay, do kinh tế khó khăn, chính quyền thành phố muốn tái sử dụng những món đồ trang trí Tết từ những năm trước đó. Một trong số đó là một dãy đèn lồng với nhiều màu sắc rực rỡ.

Dãy đèn lồng gồm ~n~ chiếc được đánh số từ ~1~ đến ~n~. Chiếc đèn thứ ~i~ có màu ~a_i~. Chính quyền muốn chọn ra một đoạn gồm ít nhất ~k~ chiếc đèn liên tiếp trong dãy để sử dụng trong năm mới, và thay thế một số chiếc đèn trong đoạn này sang một màu khác sao cho sau khi thay thế thì đoạn gồm tối đa ~x~ màu khác nhau. Chi phí để thay thế một chiếc đèn sang màu khác là ~1~ đồng.

Chính quyền muốn thử nghiệm ~q~ phương án, mỗi phương án là một cặp số ~(k, x)~ khác nhau. Với mỗi phương án, họ cần tính toán chi phí tối thiểu để có thể tạo ra đoạn đèn trang trí thỏa mãn yêu cầu.

Yêu cầu: Là một lập trình viên chuyên thực hiện những nhiệm vụ tính toán cho chính quyền thành phố, bạn hãy viết một chương trình giải quyết ~q~ phương án thử nghiệm trên trong thời gian ngắn nhất.

Dữ liệu vào

• Dòng đầu tiên gồm ba số nguyên dương ~n, q, c~ ~(1 \le c \le n \le 10^5,\ 1 \le q \le 400)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le c)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~k, x~ ~(1 \le k \le n,\ 1 \le x \le c)~.

Kết quả

• Với mỗi phương án thử nghiệm, in ra chi phí nhỏ nhất tìm được trên một dòng.

Subtask

• ~20\%~ số điểm có ~n \le 200~ và ~c = 2~.
• ~20\%~ số điểm khác có ~c = 2~.
• ~20\%~ số điểm khác có ~x = 1~ trong mọi phương án.
• ~10\%~ số điểm khác có ~q = 1~.
• ~10\%~ số điểm khác có ~k~ giống nhau trong mọi phương án.
• ~10\%~ số điểm khác có ~q \le 30~.
• ~10\%~ số điểm còn lại không có giới hạn gì thêm.

Sample Input 1

5 2 3
1 2 1 2 3
5 2
3 1

Sample Output 1

1
1

Giải thích

• Với phương án thử nghiệm đầu tiên, chính quyền phải chọn toàn bộ dãy đèn và thay thế đèn số 5 thành màu 1 hoặc 2. Chi phí nhỏ nhất là 1 đồng.
• Với phương án thử nghiệm thứ hai, chính quyền có thể chọn đoạn ~(2, 4)~ và thay thế đèn số 3 thành màu 2. Chi phí nhỏ nhất là 1 đồng.

Nguồn: Thi thử HSG9 SQRTOJ 2025 – Bài 4.