Thành phố Cuồng loạn

Cây Kruskal tái cấu trúc (Kruskal Reconstruction Tree) Quy trình xây dựng cây Kruskal tái cấu trúc: Mỗi đỉnh trong đồ thị gốc là một nút lá của cây Kruskal tái cấu trúc, ban đầu chúng không liên thông với nhau. Xét các cạnh có trọng số nhỏ trước, sau đó đến các cạnh có trọng số lớn. Nếu cạnh giúp tăng tính liên thông thì được chọn, nếu không t ...

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 ...