🎓 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

Sáng sớm, chợ nổi Cái Răng có ~N~ chiếc ghe đậu thành một hàng dài dọc theo bờ sông, đánh số từ ~1~ đến ~N~ tính từ phía cầu. Ghe thứ ~i~ chỉ bán đúng một loại trái cây, có mã loại là ~a_i~ (các ghe khác nhau có thể bán cùng một loại).

Thầy Sơn dẫn học trò đi thực tế môn "Kinh tế gia đình". Mỗi nhóm học trò sẽ được giao một đoạn ghe liên tiếp ~[l, r]~ ~(l \le r)~, chèo xuồng ghé lần lượt từ ghe ~l~ tới ghe ~r~ để hỏi giá. Bài tập của thầy là: với mỗi loại trái cây gặp được, hãy so sánh giá giữa các ghe bán loại đó. Vì vậy thầy gọi đoạn ~[l, r]~ là so giá được nếu mọi loại trái cây có mặt trong đoạn đều được bán bởi ít nhất hai ghe trong đoạn. Chẳng hạn, đoạn có các loại ~3, 5, 3, 5, 5~ là so giá được, còn đoạn ~3, 5, 3~ thì không (loại ~5~ chỉ có một ghe, không có gì để so).

Thầy Sơn có ~Q~ câu hỏi. Câu hỏi thứ ~j~ cho hai số ~L_j, R_j~: hỏi có bao nhiêu cặp ~(l, r)~ với ~L_j \le l \le r \le R_j~ mà đoạn ghe ~[l, r]~ là so giá được?

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.
• ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~L_j, R_j~ ~(1 \le L_j \le R_j \le N)~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~j~ là câu trả lời cho câu hỏi thứ ~j~.

Giới hạn (Subtask)

• Subtask 1 (~10\%~ số điểm): ~N, Q \le 100~.
• Subtask 2 (~20\%~ số điểm): ~N \le 3000~.
• Subtask 3 (~20\%~ số điểm): ~Q \le 5~.
• Subtask 4 (~20\%~ số điểm): ~L_j = 1~ với mọi ~j~.
• 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.

Sample Input 1

8 3
7 5 3 5 5 5 3 3
1 8
2 7
3 6

Sample Output 1

10
5
3

Giải thích

Có ~10~ đoạn so giá được trong cả hàng ghe: ~[2, 7]~ (5 3 5 5 5 3), ~[2, 8]~, ~[3, 7]~, ~[3, 8]~, ~[4, 5]~ (5 5), ~[4, 6]~, ~[4, 8]~ (5 5 5 3 3), ~[5, 6]~, ~[5, 8]~ và ~[7, 8]~ (3 3).

• Câu hỏi ~[2, 7]~: có ~5~ đoạn ~[2, 7]~, ~[3, 7]~, ~[4, 5]~, ~[4, 6]~, ~[5, 6]~.
• Câu hỏi ~[3, 6]~: có ~3~ đoạn ~[4, 5]~, ~[4, 6]~, ~[5, 6]~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).