Theo mình là thế này.

B1: Tạo cây IT có một nút chứa đoạn [1,n] lưu lại giá trị của tất cả phần tử lúc ban đầu (0)

B2: Đọc từng phép biến đổi và làm như sau

- Tìm các đoạn có điểm giao với đoạn [u,v] trên cây IT, gọi các đoạn tìm được là [x,y], xóa các đoạn đó và chèn các đoạn [x,y]\[u,v] lưu lại giá trị cũ nếu [x,y]\[u,v] khác rỗng. Lưu ý [x,y]\[u,v] có thể là 2 đoạn

- Chèn đoạn [u,v] lưu giá trị mới.

B3:

Đọc từng truy vấn, tìm tất cả các đoạn có điểm giao với đoạn [u,v] và in ra max của tất cả các giá trị được lưu trên các đoạn này

Độ phức tạp khoảng \(O(m \log n + q \log n)\)

Hình như có cách nhanh hơn thì phải!

Bài này làm theo kiểu lazy update là được

bạn có thể nói rõ được ko :p mình chỉ làm đc với truy vấn tăng 1 đoạn từ u đến v thôi 

Ví dụ cập nhật (u,v) =k. Nếu nút đó quản lí đó quản lí đoạn từ l,r. Xét các trường hợp:

- (l,r) nằm trong (u,v) -> set giá trị nút it đó là k

- (l,r) giao (u,v) = rỗng -> thoát.

- Còn lại -> Gán giá trị của nút it đó vào 2 nút con. Set giá trị nút it đó là một giá trị đặc biệt @ nào đó. 

Như vậy thì giá trị tại vị trí x sẽ là node đầu tiên có giá trị là @ trên cây it. Cách cập nhật là vậy