🎓 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

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

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

Mùa trái cây miền Tây, vựa của thầy Sơn bên bờ kênh Xà No có ~N~ sọt trái cây xếp thành một hàng dọc bến, đánh số từ ~1~ đến ~N~. Sọt thứ ~i~ chứa trái cây loại ~a_i~ (xoài, sầu riêng, chôm chôm, măng cụt...).

Mỗi ngày thầy Sơn nhận ~Q~ đơn hàng giao ra chợ nổi. Đơn hàng thứ ~t~ có dạng ~(l, r, k)~: thầy phải chở tất cả các sọt từ ~l~ đến ~r~ bằng chiếc ghe có đúng ~k~ khoang. Mỗi khoang chỉ được chứa một loại trái cây (nhưng chứa bao nhiêu sọt cùng loại đó cũng được), nên mỗi chuyến ghe chở được các sọt thuộc tối đa ~k~ loại khác nhau. Vì bến hẹp, các sọt phải được bốc lên ghe theo đúng thứ tự ~l, l+1, \ldots, r~: mỗi chuyến ghe chở một đoạn liên tiếp các sọt, chuyến sau tiếp nối ngay chỗ chuyến trước dừng lại.

Với mỗi đơn hàng, hãy giúp thầy Sơn tính số chuyến ghe ít nhất cần dùng. Các đơn hàng độc lập với nhau (sau mỗi đơn, các sọt lại được xếp như cũ).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 5 \times 10^4)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le N)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~l, r, k~ ~(1 \le l \le r \le N,~ ~1 \le k \le N)~ mô tả một đơn hàng.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~t~ là số chuyến ghe ít nhất cho đơn hàng thứ ~t~.

Giới hạn (Subtask)

• Subtask 1 (~10\%~ số điểm): ~N, Q \le 1000~.
• Subtask 2 (~15\%~ số điểm): mọi đơn hàng có cùng một giá trị ~k~.
• Subtask 3 (~20\%~ số điểm): ~k \le 20~ ở mọi đơn hàng.
• Subtask 4 (~25\%~ số điểm): ~k \ge 500~ ở mọi đơn hàng.
• Subtask 5 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++ là 1 giây).

Sample Input 1

9 4
3 3 3 5 5 2 1 4 1
1 9 2
2 6 1
4 9 3
1 9 5

Sample Output 1

3
3
2
1

Giải thích

• Đơn ~(1, 9, 2)~: có thể chia thành 3 3 3 | 5 5 2 | 1 4 1, mỗi chuyến không quá ~2~ loại. Cả đoạn có ~5~ loại trái cây mà mỗi chuyến chỉ chở được tối đa ~2~ loại, nên không thể dùng ít hơn ~3~ chuyến.
• Đơn ~(2, 6, 1)~: các sọt 3 3 5 5 2 chia thành 3 3 | 5 5 | 2, cần ~3~ chuyến.
• Đơn ~(4, 9, 3)~: các sọt 5 2 1 4 1 có ~4~ loại nên một chuyến không đủ; chia thành 5 2 | 1 4 1 là được ~2~ chuyến.
• Đơn ~(1, 9, 5)~: ghe có ~5~ khoang, đủ cho cả ~5~ loại, nên ~1~ chuyến là đủ.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).