Thuật toán Mo

Đoạn truy vấn dài không quá \(n\), nên giá trị \(x>n\) không thể xuất hiện đúng \(x\) lần. Bỏ qua những giá trị đó khi cập nhật tần suất.

Sắp xếp các truy vấn theo khối của đầu trái. Trong một khối, sắp đầu phải tăng hoặc giảm xen kẽ để giảm quãng đường di chuyển. Giữ một đoạn hiện tại \([L,R]\), tần suất freq[x] và đáp án:

Khi thêm hoặc xóa một phần tử có giá trị \(x\le n\):

1. Nếu freq[x] == x, trừ \(1\) khỏi đáp án.
2. Thay đổi tần suất thêm \(1\) hoặc bớt \(1\).
3. Nếu tần suất mới bằng \(x\), cộng \(1\) vào đáp án.

Điều kiện là bằng đúng \(x\), không phải ít nhất \(x\). Sau khi di chuyển tới truy vấn cần trả lời, lưu đáp án theo số thứ tự ban đầu.

Với khối dài khoảng \(\sqrt n\), Mo dùng \(O((n+m)\sqrt n)\) thời gian và \(O(n+m)\) bộ nhớ. Lời giải C++ tham khảo dùng cách này.

Phương án Fenwick cho lời giải Python

Có thể giảm số thao tác bằng cách sắp xếp truy vấn theo đầu phải rồi quét đầu phải từ trái sang phải.

Giả sử tới đầu phải hiện tại, giá trị \(x\) đã xuất hiện ở các vị trí \(p_1<\cdots<p_k\). Đặt \(p_0=0\). Nếu \(k<x\), chưa có đầu trái nào phù hợp. Nếu \(k\ge x\), những đầu trái cho đúng \(x\) lần xuất hiện tạo thành đoạn:

Mỗi giá trị \(x\) đóng góp \(1\) cho các đầu trái trong đoạn này. Dùng Fenwick trên mảng hiệu để cộng \(1\) cho một đoạn và lấy tổng tại một vị trí.

Khi gặp thêm một lần xuất hiện của \(x\), xóa đóng góp của đoạn cũ, thêm vị trí mới vào danh sách rồi cộng đóng góp cho đoạn mới. Với truy vấn \([l,r]\), quét xong vị trí \(r\) rồi lấy giá trị tại \(l\).

Phương án này dùng \(O((n+m)\log n)\) thời gian và \(O(n+m)\) bộ nhớ. Lời giải Python tham khảo dùng Fenwick; lời giải Mo vẫn là một cách giải hợp lệ.