1 solutions

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

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

    那么对于询问 [l,r][l,r],考虑二分长度 xx,那么左端点 p∈[l,r−x+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