Tóm tắt đề bài

Cho ~N~ xâu kí tự và ~Q~ truy vấn, truy vấn thứ ~i~ yêu cầu xoá đi các xâu có chứa kí tực ~i~. Sau mỗi truy vấn, cho biết số xâu kí tự còn lại.

Lời giải

Để giải bài toán này, ta cần lưu lại:

• Mảng đánh dấu ~del~ với ~del[i] = true~ khi và chỉ khi xâu thứ ~i~ đã bị xoá.
• Biến ~ans~ lưu số xâu chưa bị xoá (ban đầu ~ans = N~).

Với mỗi truy vấn ~i~, ta duyệt các xâu kí tự ~j~ từ 1 đến ~N~. Nếu xâu ~j~ chưa bị xoá và có chứa kí tự ~c_i~, ta đánh dấu xâu ~j~ đã bị xoá và giảm ~ans~ đi ~1~.

Cách làm trên có độ phức tạp ~O(NQ)~. Để cải tiến, ta nhận xét rằng: với mỗi kí tự ~c~, ta chỉ cần thực hiện tối đa một lần thao tác xoá các xâu có chứa kí tự ~c~. Do đó, ta sẽ lưu lại một mảng đánh dấu ~f~ với ~f[c] = true ~khi và chỉ khi đã thực hiện thao tác xoá đi các xâu có chứa kí tự ~c~. Với truy vấn thứ ~i~:

• Nếu ~f[c_i] = false~, ta thực hiện truy vấn rồi đánh dấu ~f[c_i] = true~.
• Ngược lại, ta không cần thực hiện truy vấn thứ ~i~.

Độ phức tạp: ~O(Q + AN)~ với ~N~ là số xâu kí tự, ~Q~ là số truy vấn, ~A~ là số kí tự latin in thường (~A = 26~).