Thành phố Cuồng loạn

Bài toán yêu cầu xử lý các truy vấn, mỗi truy vấn cho hai số l và r, cần tính tổng giá trị nhỏ nhất trên tất cả các đoạn con của đoạn [l, r]. Với các truy vấn có thể xử lý offline, ta có thể áp dụng thuật toán Mo. Vấn đề chính là tính đóng góp khi mở rộng đầu phải thêm một phần tử. Các đoạn con mới sinh ra đều có đầu phải là r. Ta cần tính tổn ...