Editorial for Bedao Regular Contest 01 - GRADE
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Vì các điểm x ~\leq 10^6~ nên ta chỉ cần sử dụng hai mảng là ~G~ và ~F~ với:
~G~ là tần suất của điểm ~K~ trong các dãy bàn liên tiếp
~F~ là giá trị lớn nhất của dãy con có điểm chung là ~K~ tại bàn thứ ~i~.
Vậy làm sao để biết được điểm K có xuất hiện trong 1 loạt các dãy bàn liên tiếp nhau không ?
Tại điểm thứ ~K~ của bàn thứ ~i~ ta sẽ tìm kiếm nhị phân ở bàn thứ ~i-1~ trước đó để xem xem điểm ~K~ có xuất hiện trong bàn thứ ~i-1~ hay không. Nếu không có thì ta sẽ gán ~G_K = 0~ vì lúc này ta không thể ghép ~2~ bàn ~i~ với ~i-1~ lại để được dãy bàn liên tiếp có điểm chung là ~K~ được. Sau mỗi lần duyệt như thế, tại điểm ~K~ đang xét tại bàn thứ ~i~, ta sẽ tăng ~G_K~ lên ~1~ và gán ~F_K = max(F_K , G_K)~.
Comments
Dòng cuối phải là ~F_K = max(F_K,G_K)~ chứ ạ ? 😃
Cảm ơn bạn đã góp ý, bên mình đã ghi nhận và sửa lại editorial rồi ạ