Mình thấy bài này không khó nhưng chỉ có vài người AC trên VOJ thôi
Chỉ khác ở chỗ các bạn thường hay lưu cây Interval dưới dạng mảng, trong đó nút con của i có chỉ số i*2 và i*2+1 nên trong bài này khi lưu đoạn 1..10^9 thì gặp khó khăn. Các bạn có thể lưu các nút vào một mảng, khi đó kích thước bộ nhớ chỉ bằng kích thước số nút thôi, hoặc cách thứ hai để giải quyết là ánh xạ các số vào dãy 1, 2, 3,...
Các bạn trong đội tuyển cài đặt thử cho quen!

Trong trường hợp này thì số nút tỉ lệ với số truy vấn phải ko?

anh Đức + Xuân Khánh đều AC= Interval Tree hả?
Em nghĩ là có thể dùng Binary Indexed Tree với bài này. Mấy anh nghĩ như thế nào ạ. Hướng làm cũng gần như Interval Tree, rõ ràng với BIT thì cứ làm bình thường là được

Dùng interval thì lấy kết quả thế nào?

Ý Khánh là sao.
Bài này tớ nghĩ BIT là vì kết quả được lấy từ đoạn 1--->i, hình như solution mà IOI đưa ra cũng là BIT mà

@Phong: lưu thế nào?
@anh Đức: theo em thấy bài này có mỗi 1 giới hạn "be bé" là "Dữ liệu vào chứa không quá 100000 dòng" --> Chẳng lẽ lưu theo cái này @_@ [shock]

Nếu cài Interval bình thường thì sẽ mất tầm 4*max nút, nếu sử dụng rời rạc hóa thì ít đi hẳn. BIT thì lưu bình thường thôi thì phải Bài này vừa đọc vừa xử lý mà

Solution của IOI là Binary Tree. Đọc chật vật mới hiểu : (