Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng tiếp cận
Gọi là chi phí nhỏ nhất để đi từ vị trí đến vị trí . Theo đề bài:
Cài đặt trực tiếp cho — quá chậm với .
Nhận xét quan trọng
Tách biểu thức trong thành hàm tuyến tính theo :
Đặt đường thẳng với . Khi đó:
Đây là bài toán cổ điển truy vấn giá trị nhỏ nhất của một họ đường thẳng tại một điểm cho trước. Vì các hệ số (slope) không nhất thiết đơn điệu, dùng Li Chao Tree.
Thuật toán
- Khởi tạo .
- Duy trì một Li Chao Tree trên miền . Mỗi nút lưu đường có giá trị nhỏ nhất tại điểm giữa của miền nút đó.
- Thêm đường với slope , intercept .
- Với :
- giá trị nhỏ nhất tại trong Li Chao Tree.
- Thêm đường với slope , intercept .
- In ra .
Li Chao Tree thực hiện cả add_line lẫn query trong .
Độ phức tạp
- Thời gian: .
- Bộ nhớ: .
Với , tổng số phép toán khoảng — đủ nhanh cho cả C++ lẫn Python.
https://oj.chuyentin.pro/problem/chtline/editorial
Bình luận