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.

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 POSTDELETE, 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

Please read the guidelines before commenting.


There are no comments at the moment.