Editorial for Tìm kiếm động cơ
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Ta sẽ xử lý bài toán offline.
Đầu tiên xây cây trie từ tất cả các truy vấn POST
. Sau đó ta duyệt và
dựng Euler tour từ cây đó. Cuối cùng ta dựng cây phân đoạn để duy trì
các xâu đang bật.
Với mỗi truy vấn POST
và DELETE
, ta gán vị trí tương ứng trên cây
phân đoạn là 1 hoặc 0.
Để tìm xâu có thứ tự từ điển thứ ~k~, ta duyệt dfs theo thứ tự các con từ bé đến lớn. Khi đó, để tìm xâu thứ ~k~ ta chỉ cần bò trên cây phân đoạn để tìm tiền tố ngắn nhất trong đoạn biểu diễn cây con chứa sâu ~s~ có tổng là ~k~.
Comments