Hướng dẫn giải của Free Contest 133 - CHARCNT
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 làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Sử dụng CTDL ~Segment Tree~.
Thay vì sử dụng ~26~ cây ~ST~ để lưu ~26~ chữ cái khác nhau, ta có thể coi chữ cái ~c~ biểu diễn bit thứ ~c-~'~a~'. Từ đó có thể sử dụng một cây ~ST~ duy nhất.
Mỗi bit ~i~ của nút thể hiện chữ cái thứ ~i~ có xuất hiện trong đoạn mà nút quản lí hay không. Nút ~i~ bằng hợp của nút ~2\times i~ và ~2\times i+1~. Kết quả là số bit ~1~.
Bình luận