Hướng dẫn cho AtCoder ABC327 F - Hứng táo
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Quét thời gian, cập nhật vị trí đặt giỏ
Vì thời gian và vị trí của táo đều nguyên, giỏ nhận các quả có \(S\le T_i\le S+D-1\) và \(L\le X_i\le L+W-1\).
Sắp táo theo thời gian. Giữ một cửa sổ các quả có thời gian từ \(T-D+1\) tới \(T\), với \(T\) là thời gian đang xét. Khi thêm một quả ở vị trí \(x\), mọi vị trí đặt giỏ
đều nhận thêm một quả. Khi quả hết thời hạn, trừ \(1\) trên cùng đoạn. Dùng Segment Tree có lazy để cộng đoạn và lấy giá trị lớn nhất toàn cây. Giá trị lớn nhất qua mọi cửa sổ là đáp án.
Chỉ cần lưu \(L\) từ \(1\) tới \(\max X_i\): một vị trí lớn hơn không nhận được quả nào. Nếu cây được mở rộng tới lũy thừa của \(2\), các ô dư vẫn bằng \(0\) và không làm tăng đáp án.
Chứng minh
Với mỗi quả \(x\), bất đẳng thức \(L\le x\le L+W-1\) tương đương \(x-W+1\le L\le x\). Các cập nhật vì thế giữ đúng số táo đang có trong cửa sổ cho từng vị trí \(L\).
Một cách đặt giỏ tối ưu nhận được ít nhất một quả. Gọi \(T\) là thời điểm rơi muộn nhất trong số táo nhận được. Chuyển cửa sổ thời gian thành \([T-D+1,T]\) không mất quả nào đã nhận. Khi đầu trái này nhỏ hơn \(1\), chọn \(S=1\) vẫn giữ mọi quả đó vì thời gian rơi đều dương. Sau khi thêm hết táo ở thời điểm \(T\), vòng quét xét đủ cửa sổ này, nên tìm được ít nhất số táo của cách đặt tối ưu. Ở các bước còn lại, số táo đang giữ không lớn hơn số táo một cách đặt giỏ hợp lệ có thể nhận, vì thế đáp án không thể lớn hơn tối ưu.
Mỗi quả được thêm và bỏ nhiều nhất một lần. Đặt \(M=\max X_i\); thời gian là \(O(N\log N+N\log M)\) và bộ nhớ là \(O(N+M)\). Trong cây của hai chương trình, nhãn cộng ở cha được giữ riêng; sau khi sửa con, lấy max của hai con rồi cộng nhãn của cha, nên không cần đẩy nhãn xuống trước mỗi lần cập nhật.
Bình luận