Subtask 1: Trâu

Subtask 2:

• Ta tạo một cây Segment Tree hay BIT cho mỗi giá trị từ ~1~ đến ~10~. Với mỗi truy vấn, ta kiểm tra với từng giá trị số lần xuất hiện trong đoạn ~[l,r]~.

Subtask 3:

• Ban đầu, thuật toán cho subtask này là sử dụng Segment Tree + offline, nhưng do giới hạn hơi nhỏ nên có nhiều bạn dùng Mo vẫn qua được. Dưới đây trình bày cách sử dụng Segment Tree.
• For từ ~1~ tới ~n~, xét vị trí ~i~, nếu ~A_i~ xuất hiện chưa quá ~k~ lần thì chưa cần làm gì.
• Ngược lại, nếu ~A_i~ xuất hiện tới lần thứ ~p \ge k~, ta sẽ update vị trí xuất hiện của ~A_i~ thứ ~p-k~ là ~1~ và ~p-k-1~ là ~-1~.
• Mỗi khi gặp ~A_i~ thì xóa các giá trị cũ và thực hiện update lại.
• Với mỗi truy vấn thì tổng từ vị trí ~l~ đến ~r~ trên Segment Tree là đáp án.

Subtask 4:

• Chia căn các truy vấn, xử lí từng cụm căn truy vấn một ~([1, \sqrt{q}], [\sqrt{q}+1...2 \times \sqrt{q}]...)~.
• Khi xét đến block thứ ~i~ đảm bảo thực hiện tất cả các truy vấn cập nhật từ block ~i - 1~ trở về trước.
• Bây giờ tính đáp án cho ~\sqrt{q}~ truy vấn trong block ~i~, tính offline đáp án cho các truy vấn mà chưa sử dụng các truy vấn update trong block này trước.
• Bây giờ với mỗi truy vấn sau khi tính offline xong, với mọi truy vấn update trước nó trong block ~i~, kiểm tra xem nó có làm thay đổi đáp án hiện tại không rồi cập nhật đáp án mới, có tối đa ~\sqrt(q)~ truy vấn update.
• Độ phức tạp: ~\mathcal{O}((n \log n + q) \sqrt q)~.