1 solutions

  • 0
    @ 2023-5-29 21:29:16

    我们考虑先预处理出对于每一个 iil=il=i 时的最长完美子段长度,设为 gig_i

    那么对于询问 [l,r][l,r],考虑二分长度 xx,那么左端点 p[l,rx+1]p \in [l,r-x+1]

    我们求出 gpg_p 最大值,如果大于等于 xx,则存在 x\geq x 的子段。

    预处理可以二分+主席树,询问二分+RMQ,整体下来两只 log\log

    口胡的。

    • 1

    Information

    ID
    123
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    10
    Tags
    # Submissions
    8
    Accepted
    4
    Uploaded By