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.

Author: bedao

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

Please read the guidelines before commenting.



  • 3
    vidut_206_CNH   commented on Oct. 5, 2021, 6:50 p.m.

    Dòng cuối phải là ~F_K = max(F_K,G_K)~ chứ ạ ? 😃


    • 3
      ntkwan   commented on Oct. 6, 2021, 11:26 a.m.

      Cảm ơn bạn đã góp ý, bên mình đã ghi nhận và sửa lại editorial rồi ạ