Phân rã căn bậc hai: Thuật toán Mo đếm phần tử phân biệt
Hệ thống giám sát bảo mật của AI Empire Academy ghi nhận N mã sự kiện A1, A2, …, AN (1 ≤ Ai ≤ 105). Đội ngũ vận hành cần trả lời Q câu hỏi ngoại tuyến: trong đo
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: struct, std sort, custom comparator.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu nguyên lý phân rã căn bậc hai (Square Root Decomposition) và xử lý truy vấn ngoại tuyến (Offline Processing).
- Cài đặt cấu trúc sắp xếp các truy vấn theo khối: Khối ⌊ L / B ⌋ và điều kiện tối ưu thứ tự của R.
- Duy trì mảng đếm tần số freq[] với hai hàm mở rộng/thu hẹp cửa sổ add và remove trong O(1).
- Đạt độ phức tạp thời gian O((N + Q)√(N)).
Mô tả bài toán
Hệ thống giám sát bảo mật của AI Empire Academy ghi nhận N mã sự kiện A1, A2, …, AN (1 ≤ Ai ≤ 105). Đội ngũ vận hành cần trả lời Q câu hỏi ngoại tuyến: trong đoạn sự kiện từ vị trí L đến R, có bao nhiêu mã sự kiện phân biệt (các giá trị khác nhau)?
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
- Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
- Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N và Q (1 ≤ N, Q ≤ 105).
- Dòng 2: N số nguyên A1, A2, …, AN (1 ≤ Ai ≤ 105).
- Q dòng tiếp theo: Mỗi dòng gồm 2 số nguyên L, R (1 ≤ L ≤ R ≤ N).
Output
- In ra Q dòng, mỗi dòng là số lượng phần tử phân biệt của truy vấn tương ứng theo đúng thứ tự ban đầu.
Ràng buộc
- 1 ≤ N, Q ≤ 105.
- 1 ≤ Ai ≤ 105.
- 1 ≤ L ≤ R ≤ N.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
5 3
1 1 2 1 3
1 5
2 4
3 5
Output
3
2
3
*Giải thích:*
Đoạn [1, 5]: {1, 1, 2, 1, 3} có 3 giá trị phân biệt là {1, 2, 3}.
Đoạn [2, 4]: {1, 2, 1} có 2 giá trị phân biệt là {1, 2}.
Đoạn [3, 5]: {2, 1, 3} có 3 giá trị phân biệt là {2, 1, 3}.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
