Hướng dẫn giải của Tìm kiếm động cơ
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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~.
Bình luận