Solutions of Segment queries

Select solution language

lenhanbo Created at 11 likes

Khi ta đang xét đoạn các truy vấn từ $[l,r]$. Gọi $mid = (l+r)/2$, ta sẽ tính toán những đáp án của các cập nhật thêm vào trong đoạn $[l,mid]$ làm tăng đáp án cho các truy vấn trong đoạn $[mid+1,r]$. Vì ở đây các cập nhật luôn xảy ra trước các truy vấn ta tính nên thứ tự thời gian không còn quan trọng nên ta có thể sort các truy vấn và cập nhật trong đoạn $[l,r]$ theo đầu mút trái $(l)$ giảm dần. Sau đấy ta sẽ duyệt qua toàn bộ những truy vấn và cập nhật sau khi đã sort, khi gặp cập nhật mà có thứ tự xuất hiện trong đoạn $[l,mid]$ thì ta sẽ dùng cây BIT để lưu lại đầu r, còn khi gặp truy vấn mà có thứ tự thời gian xuất hiện thuộc đoạn $[mid+1,r]$ thì ta sẽ dùng cây BIT để đếm toàn bộ những cập nhật có đầu mút phải ($r_j$ >= $r_i$). Như vậy ta đã giải quyết bài toán trong độ phức tạp là $O(n \times log^2(n))$