Chúng ta sẽ sử dụng chia căn để truy vấn giải quyết bài toán này. Ý tưởng của thuật toán như sau:

Lời giải

- Dễ dàng nhận thấy số số a có tính chất ~a\ AND\ s=a~ chỉ là các số thuộc dãy số là submask của ~s~.

- Gọi ~freq[i]~ là số lần xuất hiện của ~i~ trong dãy số, ~dp[i]~ là số số trong dãy số là submask của ~i~. Mảng ~freq~ có thể được tính nhanh trong ~O(1)~, còn kết quả của ~dp~ có thể được tính dựa trên mảng ~freq~ trong ~O(n\log n)~ với ký thuật DP SOS (DP Sum over Subsets), với ~n~ là giới hạn của các số ~s~ trong dãy.

- Ta chia truy vấn thành các block có size ~B~. Trước khi xử lý từng block thì ta sẽ sử dụng DP SOS để tính mảng ~dp~ lưu kết quả của những block trước đó. Đối với các truy vấn ~cnt~ thì ta sẽ trả lời truy vấn bằng mảng ~dp~. Tuy nhiên, kết quả vẫn chưa bao gồm các số được thêm hoặc xóa ở block hiện tại nên ta duyệt trâu qua các truy vấn ~add~ và ~del~ ở block hiện tại để tính kết quả.

Phân tích

- Với các truy vấn ~sum~ và ~del~, ta cập nhật kết quả trong ~O(1)~

- Với mỗi truy vấn ~cnt~, ta duyệt lại các truy vấn cập nhật cùng block nên tổng độ phức tạp là ~O(q\ \cdot\ B)~

- Với mỗi block ta sẽ làm DP SOS ~1~ lần nên độ phức tạp của từng block là ~O(n\log n)~, có ~\lceil\frac{q}{B}\rceil~ blocks nên độ phức tạp tổng của bước này sẽ là ~O(\frac{q}{B}\cdot n\log n)~

- Tổng độ phức tạp của thuật toán là: ~O(q\ \cdot\ B\ +\ \frac{q}{B}\cdot n\log n)~, sẽ được tối ưu nhất với ~B \approx 1024~

- Bài này vẫn có thể giải được bằng kỹ thuật Meet in the middle, tuy nhiên chúng mình sẽ không phân tích về cách làm này ở đây