Hướng dẫn bài COLTREE - Màu của cây

Link đến trang bài tập

Dễ thấy bằng việc lưu trữ thứ tự DFS, ta có thể chuyển đổi bài toán này thành bài toán: Cho một mảng phần tử khác nhau và truy vấn, mỗi truy vấn yêu cầu in ra số lượng giá trị khác nhau trong một khoảng từ tới . Trả lời tất cả truy vấn đó.

Phát biểu theo một cách khác sẽ là: Với mỗi khoảng truy vấn từ tới , có bao nhiêu màu sắc mà vị trí xuất hiện đầu tiên không nhỏ hơn của nó là không lớn hơn R.

Sort tất cả truy vấn theo trước, nếu bằng nhau thì sort theo (ta lưu trữ lại chỉ số của từng truy vấn để in câu trả lời theo đúng thứ tự về sau). Định nghĩa mảng là vị trí tiếp theo trong mảng có cùng màu với phần tử thứ (nếu là phần tử cuối cùng có màu đó thì ), một cây BIT tính tổng và một biến . Quy trình duyệt như sau:

• , với là các lần xuất hiện đầu tiên của mỗi màu sắc.
• Khi xét tới truy vấn :
  • Chừng nào , ta và , sau đó tăng lên . Như vậy cây BIT sẽ đảm bảo là chỉ mang giá trị ở các vị trí không nhỏ hơn , và do ta sort các truy vấn theo nên sẽ chỉ cần tăng, không bao giờ giảm.
  • Kết quả của truy vấn là .

Độ phức tạp: .

Lưu ý:

• Bài này có test rất hiểm, không thể dùng DFS đệ quy được mà phải thực hiện DFS không đệ quy.
• Dữ liệu đầu vào lớn, phải dùng nhập xuất nhanh (scanf, printf chẳng hạn).