Thành phố Cuồng loạn

Tổng quan bài toán Bài toán yêu cầu quản lý một cấu trúc cây, trong đó các đỉnh có thể được kích hoạt hoặc vô hiệu hóa theo thời gian thực. Với mỗi trạng thái, cần tính toán tổng trọng số cạnh nhỏ nhất để nối tất cả các đỉnh đang được kích hoạt lại với nhau thành một thành phần liên thông. Phân tích thuật toán Giả sử các đỉnh đang hoạt động đư ...

### CF1879F *2800 ★ Giá trị của một điểm được tính bằng h_i * ceil(a_i / x). Bước đầu tiên là sử dụng phương pháp phân đoạn trực tiếp, chia thành sqrt(n) khoảng và duyệt qua từng khoảng sẽ có độ phức tạp là O(Tn * sqrt(a_i)). Tuy nhiên không có bảo đảm về tổng n, nên ta cần tìm cách sử dụng log. Nhớ lại chuỗi điều hòa, khi liệt kê x, các phần t ...